Cyfrowe przetwarzanie tekstu
Spis treści
- Wstęp
- ASCII Art
- Gry tekstowe
- Język naturalny
- Wyszukiwanie
- Języki opisu
- Języki programowania
- Zakończenie
Wstęp
Choć podobno obraz mówi więcej, niż tysiąc słów, nigdy nie uda mu się
całkowicie wyprzeć tekstu z naszego życia. Nawet w dobie telewizji i
multimediów czytanie książek pozostaje zajęciem ciekawym i potrzebnym,
a wszelkie kolorowe magazyny czy nawet reklamy są tylko atrakcyjną
wizualnie otoczką dla informacji niesionych przez litery i cyfry.
Tekst a komputer
Także w dziedzinie techniki cyfrowej tekst odgrywa wielką rolę. Można
powiedzieć, że jest on najdoskonalszą formą komunikacji człowieka
z maszyną. Oto schematyczne przedstawienie ich wzajemnych relacji:
Podobnie można przedstawić kilkupoziomowy proces programowania
komputera:
Zastosowania tekstu
- Jako sposób przekazywania informacji
- Napisany przez jednego dokument może dla wielu stanowić źródło wiedzy
i informacji, np. książka, artykuł czy strona WWW.
- Jako forma komunikacji
- Za pomocą tekstu można się porozumiewać tam, gdzie niemożliwe jest to
bezpośrednio czy za pomocą głosu, np. poczta tradycyjna i elektroniczna, IRC.
- Jako język opisu
- W niektórych zastosowaniach dane używane przez programy wygodnie jest
tworzyć i przechowywać w specjalnie opracowanych formatach tekstowych, np. XML.
- Jako język programowania
- Język (czyli zbiór reguł składniowych i semantycznych) wystarczająco podobny
do języka naturalnego, by człowiek mógł po jego opanowaniu sprawnie formułować w nim
swoje pomysły, a zarazem dostatecznie ścisły, by mógł być w sposób automatyczny
przetwarzany przez komputer, to najlepsza metoda programowania.
Co można robić z tekstem?
- Przechowywać i przesyłać
- Jak każde dane
- Wprowadzać i wyprowadzać
- Pobierać od użytkownika i pokazywać użytkownikowi
- Generować
- Tworzyć za pomocą specjalnych algorytmów
- Przeszukiwać
- Sprawdzać obecność pewnych wyrazów
- Parsować
- Analizować wg składni języka, w którym jest zapisany
- Wykonywać
- Jeśli jest kodem w jakimś języku programowania
Wstęp właściwy :)
Po powyższym wstępie zapraszam na podróż do fascynującego świata tekstu
i metod jego przetwarzania za pomocą komputera. Choć może na pozór nie jest
on tak atrakcyjny, jak świat programowanie grafiki czy nawet dźwięku, to jednak
jest nie mniej od nich ważny i zapewniam, że przy odpowiednim podejściu
równie ciekawy.
Artykuł ten przeznaczony jest dla osób zajmujących się programowaniem.
Jednak nie znajdzie się tu zbyt wiele kodów źródłowych. Tym bardziej nie
jest jego celem nauka programowania. Opisane zostaną w sposób abstrakcyjny
różne pojęcia i od Twojego stopnia zaawansowania zależy, czy jesteś je
w stanie zaimplementować.
Ten artykuł to efekt mojego zainteresowania wszystkim, co tekstowe
w komputerze i w programowaniu. Stanowi próbę przeglądu różnych zagadnień,
a wiele z nich opisane jest bardzo skrótowo. W końcu nie na wszystkim,
o czym tutaj napisałem, znam się dobrze i gdzieniegdzie chciałem tylko
zasygnalizować pewne rzeczy zachęcając Cię to samodzielnego ich
zgłębiania.
Omawiane tematy ułożone są w kolejności od najprostszych (nie od razu
nawet bezpośrednio związanych z programowaniem) do coraz bardziej
zaawansowanych. Na końcu wielu podrozdziałów znajduje się zbiór odsyłaczy
do ciekawych stron WWW.
Problem kodowania
Początkowo planowałem umieścić tutaj wstęp do programowania tekstu wraz
z opisem używanych do tego celu typów danych w języku C++ itp. Choć
ostatecznie postanowiłem pozostawić wszelkie sprawy czysto programistyczne
poza zakresem tego artykułu, to przed rozpoczęciem właściwego artykułu
nie mogę nie wspomnieć o istotnym problemie, który pojawia się w związku
z koniecznością kodowania polskich liter.
ASCII
W celu zakodowania tekstu przyporządkowano każdej liczbie (kombinacji
bitów) pewien znak. Tak powstał kod ASCII. Do zakodowania jednego znaku
używa on jednego bajta (8 bitów). Dostępnych jest więc 256 różnych znaków.
Standard ten obowiązuje już od czasów systemu DOS aż po dziś dzień.
Tak naprawdę, sam standard ASCII wykorzystuje 7 bitów. Oznacza to, że
dostępnych jest 128 różnych kombinacji bitów, czyli można zapisać 128 różnych
znaków. Taka ilość wystarczyła, by pierwszym 32 znakom (odpowiadającym
zakodowanym w systemie binarnym liczbom naturalnym 0...31) przypisać pewne
specjalne kody sterujące, a dalej zmieścić cyfry, małe i duże litery alfabetu
łacińskiego oraz wszystkie znaki znajdujące się na klawiaturze.
256 możliwych kombinacji bitów w jednym bajcie to jednak za mało, by
zapisać znaki specyficzne dla różnych języków świata, jak polskie
"ąćęłńóśżź" czy niemieckie "umlauty" (nie mówiąc już o zupełnie innych
alfabetach, jak cyrylica czy znaki chińskie).
Dlatego dodatkowe 128 znaków powstałe po użyciu ósmego bitu nie jest
ujednolicone. Stworzonych zostało wiele tzw. stron kodowych (ang. "codepage")
używających tych dodatkowych znaków do kodowania liter alfabetów
narodowych, a przy tym różnych symboli graficznych i innych bardziej lub
mniej przydatnych. Jest z tym niestety dużo problemów. Nawet dla samego
języka polskiego powstało kilka kodów.
W wielu zastosowaniach, szczególnie w Internecie (WWW, e-mail)
w nagłówku zapisywana jest nazwa standardu kodowania użyty w danym
dokumencie. Pozwala to zmniejszyć problemy wynikające z całego tego
bałaganu.
Unikod
Rozwój Internetu stworzył konieczność wynalezienia lepszego sposobu
kodowania znaków, niż wysłużony już kod ASCII. Nawet ze swoimi stronami
kodowymi ten ostatni ma wiele ograniczeń i sprawia wiele problemów. Nie
można chociażby zapisać tekstu w kilku różnych językach w jednym
dokumencie.
Pomyślano więc tak: Właściwie, skoro dzisiejsze dyski mają pojemności
mierzone w gigabajtach, a obrazki i filmy zajmują o całe rzędy wielkości
więcej miejsca niż tekst, po co nadal ograniczać się do jednego bajta na
znak? Dlaczego nie utworzyć kodu, w którym jeden znak zajmowałby,
powiedzmy, 2 bajty?
Tak powstał Unikod (ang. "Unicode", w skrócie UCS). Warto zdać sobie
sprawę z faktu, że już za pomocą 2 bajtów można zakodować 2162 = 65536
różnych znaków! Dlatego w unikodzie znalazło się miejsce dla wszelkich
użytecznych i używanych na świecie liter, symboli i znaków, a po
upowszechnieniu się tego standardu nasze dzieci będą już tylko od nas
słyszały historie, jakie to kiedyś były problemy w komputerze z
kodowaniem znaków :)
Najpopularniejszymi odmianami unikodu są UTF-8 i UTF-16. W tej pierwszej
znak może mieć różną długość. Pierwsze 128 znaków pokrywa się z tablicą
ASCII i jest zapisywana za pomocą jednego bajta, natomiast znaki dodatkowe
(np. polskie literki) są zapisywane za pomocą specjalnych kilkubajtowych
sekwencji. Z kolei UTF-16 określa standard, w którym każdy znak zajmuje
2 bajty.
Polskie litery
Oto tabela kodów polskich liter w ważniejszych stronach kodowych
(cytowana za Polską Stroną Ogonkową):
(a) (c) (e) (l) (n) (o) (s) (x) (z)
ą ć ę ł ń ó ś ź ż
---------------------------------------------------------------------------
ISO-8859-2 177 230 234 179 241 243 182 188 191
Windows-1250 185 230 234 179 241 243 156 159 191
IBM (CP852) 165 134 169 136 228 162 152 171 190
brak 97 99 101 108 110 111 115 122 122
Unicode 0x0105 0x0107 0x0119 0x0142 0x0144 0x00F3 0x015B 0x017A 0x017C
(A) (C) (E) (L) (N) (O) (S) (X) (Z)
Ą Ć Ę Ł Ń Ó Ś Ź Ż
---------------------------------------------------------------------------
ISO-8859-2 161 198 202 163 209 211 166 172 175
Windows-1250 165 198 202 163 209 211 140 143 175
IBM (CP852) 164 143 168 157 227 224 151 141 189
brak 65 67 69 76 78 79 83 90 90
Unicode 0x0104 0x0106 0x0118 0x0141 0x0143 0x00D3 0x015A 0x0179 0x017B
- ISO-8859-2 (Latin-2)
- To oficjalny standard kodowania ustalony jako norma, zalecany do
używania w Internecie i używany w systemie Linux.
- Windows-1250
- Przez wielu potępiany za to, że został wylansowany przez Microsoft.
W praktyce jednak to właśnie jego używa system Windows, a wielu miejscach
Internetu jest on nie mniej popularny, niż ten pierwszy.
- IBM (CP852)
- Standard używany w systemie DOS, a obecnie na konsoli Windows.
- brak
- Kody liter standardowych odpowiadających danym polskim literom.
- Unicode
- Dwubajtowe kody polskich liter w unikodzie zapisane w systemie
szesnastkowym.
Aby sprawdzić, czy prawidłowo działają w jakimś programie, systemie czy
gdziekolwiek indziej polskie litery, wpisuje się zazwyczaj utarty tekst:
"Zażółć gęślą jaźń". Choć nie ma on większego sensu, ma to do siebie, że
będąc poprawnym gramatycznie zdaniem zawiera w sobie wszystkie polskie
literki.
Inne znaki specjalne
Dodatkowo standard Windows-1250 przewiduje kilka znaków specjalnych,
które podczas konwersji na inne strony kodowe także trzeba zamieniać:
- Cudzysłów dolny (132 = 0x84) - zamieniać na zwykły cudzysłów "
- Cudzysłów górny (148 = 0x94) - zamieniać na zwykły cudzysłów "
- Odwrócony cudzysłów górny (147 = 0x93) - zamieniać na zwykły cudzysłów "
- Wielokropek (133 = 0x85) - zamieniać na trzy kropki "..."
- Krótszy myślnik (150 = 0x96) - zamieniać na zwykły myślnik "-"
- Dłuższy myślnik (151 = 0x97) - zamieniać na zwykły myślnik "-"
- Apostrof (146 = 0x92) - zamieniać na zwykły apostrof '
Białe znaki
Pośród znaków ASCII wydzieloną grupę stanowią tzw. białe znaki (ang.
"whitespace") albo inaczej odstępy. Są one uznawane za znaki oddzielające
pewne części tekstu. Należą do nich 4 znaki:
- 0x09 (9) "\t" HT - tabulacja
- 0x0A (10) "\n" LF - koniec wiersza
- 0x0D (13) "\r" CR - powrót karetki
- 0x20 (32) " " - spacja
W wielu językach (w tym w językach programowania, np. C++ czy Pascal
oraz w językach opisu, np. HTML czy XML) fakt, jakie spośród tych znaków
wystąpią, w jakiej ilości i w jakiej kolejności, nie ma znaczenia - każda
taka sekwencja traktowana jest jako pojedynczy odstęp. To dzięki temu możemy
robić wcięcia w kodzie i swobodnie go rozmieszczać (zauważ, że wcięcie to
znak końca wiersza plus pewna liczba spacji lub tabulacji). Takie
traktowanie odstępów w jakimś języku nosi nazwę wolnego formatu zapisu.
Znaki końca wiersza
Poświęcenia dodatkowej uwagi wymaga temat znaków uznawanych za koniec
wiersza (linii) w tekście. Panują w tej kwestii dwa różne standardy.
- W Windows koniec wiersza zaznacza się sekwencją dwóch znaków: CR i LF
- W Linux samym LF
- W Mac samym CR
Z kompatybilnością między tymi formatami bywa różnie. W Linux podwójny
koniec wiersza najczęściej zinterpretowany zostanie prawidłowo, o ile wiersz
może kończyć się odstępem i ten odstęp zostanie zignorowany.
Notatnik Windows nie odczyta poprawnie dokumentu zapisanego ze znakami
końca wiersza w stylu linuksowym. Na prawidłowe jego wyświetlenie możesz za
to liczyć w programie Lister wbudowanym w Total Commander.
Aby edytować i zapisywać pod Windows dokumenty ze znakami końca wiersza
w stylu linuksowym, możesz użyć jednego z tekstowych edytorów HTML, np.
HomeSite lub Pajączek. Trzeba tylko uaktywnić specjalną opcję
w konfiguracji. Nazywa się ona najczęściej zapisywaniem znaków końca
wiersza w stylu Unix.
Linki
- Polska Strona Ogonkowa
- Serwis poświęcony problemom kodowania polskich znaków
- ASCII Table
- Tablica znaków ASCII
- Unicode Home Page
- Oficjalna strona standardu Unicode
ASCII Art
ASCII Art to sztuka tworzenia grafiki za pomocą odpowiednio ułożonych
znaków tekstowych. Jej zwolennicy twierdzą, że to najbardziej
naturalna dla komputera i najbardziej przenośna forma grafiki (działa
wszędzie). Jej tworzenia można się prosto nauczyć, chociaż nie obejdzie
się bez odrobiny talentu graficznego.
Wbrew pozorom, zajmowanie się tym niszowym działem grafiki nadal ma sens.
Czysty, niesformatowany tekst (czyli niemogący zawierać
liter różnych krojów, kolorów czy wielkości) nadal spotykamy w wielu
miejscach, np. w e-mailach, IRC, grupach dyskusyjnych oraz w plikach
typu "Readme" dołączanych do większości programów i zapisanych
w nieśmiertelnym formacie TXT.
Za pomocą ASCII Art można rysować schematy, tabele, robić
obramowania i różne ozdoby wokół tekstu, a także po prostu tworzyć rysunki.
Do grafiki ASCII najczęściej używa się tekstu w jednym kolorze pisanego
czcionką nieproporcjonalną (czyli taką, w której każdy znak, zarówno "m"
jak i "l", mają taką samą szerokość), np. Courier New czy Fixedsys.
Dawniej wykorzystywano w tym celu pełną gamę 256 znaków ASCII razem
z różnymi symbolami i "płotkami", których wygląd zależy od użytej strony
kodowej. Takie, nie zawsze wyświetlane poprawnie pliki można dziś spotkać
np. w crackach do różnych programów. Aby poprawnie obejrzeć taki plik,
należy otworzyć go w programie Total Commander klawiszem [F3] (podglądnąć
za pomocą Listera) i nacisnąć [S] (tryb "ASCII (DOS Charset)"). Do tworzenia
ASCII Art najlepiej używać tylko standardowych liter i innych znaków
dostępnych bezpośrednio na klawiaturze.
ASCIIzacja
:,:;::.o.;:,3:,::.;,,:,,7,:::::::::, MANNMMMMMMMMMMMMM@RM :::;;;;;;;;;77o7M
;..;., 2.7;.u:,::,3ooo3o3:::::::::,. MRM 3MMM :;;::;:;;;;;;;;,3
:. ;., 3 7: Z;.,... . .........,,. MMM ;7o;:obR;7o o8M ,,:::;;;;;;;;;;:o
;,.: 7 :, 3:,;;;7777oooooo7oo7777;., ,7722RMMMM,2MM:.Mu8oo7;;;;;;;;;;7:7
;.. ::3o3oo333333oooo7777;;;;;;:,.. 3bNA8. , 3 . .;::;;;;;;;;;7
;. ,M2oo7oo;;;;;;;;;;;::::;,,....;2EM@8; :38bAu;,7.,. .:;;;;;;;;;
; bR27;,:;;;;7;;;;;;;;:::7o28RMMMA, . :2 ,3Z888b8bRZEEE@MHNR :;;;;;;;;
7 8Uu7;::;77777;;7o28AEMMMH@R87 . Z32NMU377ooo72U7AHH8,,RM..;;;;;;;;
7 .@u7;:::;;o2uZUHNR83; .. bZ8U3 ..;ZRU8ZUo.HU3RRb3 ,;;;;;;;
7. MZ2o;7;;:;7@Z2 .,. .. . MA28b:..;uAU8u23o773o2bbu33bu :;;;;;;
o . Rb3oooo3322bo .;; ... @M2bu3 288RUZ3;::,.,,,,,;2REAA :;;;;;;
o . NZ8883:. . .. MMER8b7:733R@827;;;;;;:. .,,,.uAM;;;;;;:;
3 M8; .. ... .. EM@AAR8ou,72MU2337: .,;;::::;o; o ;.:;;;;;
3 . . . . AMMHRAbA;8,7.E;:3Z8u:ou8. .,,,,:;,8N o;:::::;
2 ,3..,::,:7;:,, HMMH@@RARuAo;288oo;;ZMMM8MNR2; MU ;;
2 2Z;,. . ,: 2RMZ MMHER@@Rb8AR.o2M223;, .2;.732;;MMMMH8M ;.MMNMNE
2 Zo.,,,. ,3EUHMNM3 M@EHHRuRU882 7;M3ZZ3;: ,77 ;RU.8oMM :; uUbAA8
2 , Z2::, ;uuo:,;;3;MM3bNHEAZ83bAZu,;u@7uZ237;;723oo 7 oH2 ;7,.RZZUU
3. : 3M7. 3Z2o7;;:,:8MHHM ENZZu78H22o;:;R7o2333;.7bAR3 u7 2M;;::;; RuUUo
3; ,;. ,uMAZoo7777;,,7@M@@M M2uZ2Moo;823;@:3272ZHAu7,.,:Uo:@Ho77;;:; MMMMM
o; ::, 7 Hb237777o7:,;8ZEME.NU82N3,R M287URo37oo2AUZUMU3:bMUo:;7;:;;:,
77 ,.:: 7 NZ2777oo7:.;ZuZRHMHH ER U ubbH:ZRbZ2;. ;oo , M@Zb3;;;;:,;77.,,:
77.,,:, ;; AAu37;7o7;,7ZZ2uUHHM.Mo,b RAbM 8R@RRAbu27: RMbHAHH2:,:;:::;u:;;;
77..::;,;o Hboo;7777;72u332Z@M8M.8: HHU8o@EEAUb8233U33,MM83u3;::::::,3
77:::;:.:7,..Hb237;:;;7oZ23oouAMN b;8MH8uZ3o7;:,.,722@AMA2o77:,,;,::;:.H@@E
77,::;::,3,; N8233oo777uuu23;;ZR:8u@RR@b;::7777o223EEuUo7;7o;:::::,:: NMHE
7o:;:;;:,3:;; ;A228u;;o;o32uu8Zu88o28uo;;;o32322u38bZ377;77;7::;;;;:,, @HRR
7o:;;;:;,o:;;.3 EZ2u2;77o237o322u283uo77ooo3333o3o377;7;;;;77.,::;;::. MERR
77:,;;::.o:;;,2 7b223;oo327;7;;;;;;777o7oo7o7o7777o77777;;;7o:::::::. UMERR
77;;;;;;;o;;7;u; b23oo332u33333o77777777737777ooo7ooooooo777o::;:,:;:3M@RRR
To jest przykład zdjęcia skonwertowanego automatyczne do postaci
tekstowej w programie ASCII Generator. ASCIIzacja to proces przetwarzania zwykłego
obrazu na ASCII Art poprzez pewne przekształcenie, które każdej grupie pikseli
obrazka przyporządkowuje jakiś znak.
Można to zrealizować w taki sposób:
- Wstępnie przetworzyć obrazek - okroić, zmienić rozmiar (przeskalować),
zmienić jasność czy kontrast
- Przetworzyć obrazek na postać lepiej nadającą się do ASCIIzacji -
rozmyć lub wyostrzyć, wykryć krawędzie czy zastosować dowolne inne efekty
(filtry)
- Zamienić go na postać pośrednią - np. z kolorów RGB na skalę szarości
wg wzoru (ten wzór uwzględnia czułość ludzkiego oka na poszczególne składowe):
I = 0.3*R + 0.59*G + 0.11*B
- Każdej prostokątnej grupie pikseli przyporządkować jakiś znak
Tą ostatnią czynność można wykonać na wiele sposobów. Najprostszym
jest skonstruowanie ciągu znaków uporządkowanych według "stopnia
zaciemnienia" i wybieranie ich na podstawie średniej jasności danego prostokąta
na obrazku. Takim zestawem znaków może być np. (na początku jest spacja):
.:-;!/>)|&IH%*#
Innym podejściem jest rozpoznawanie układu jaśniejszych i ciemniejszych
podobszarów takiego prostokąta (po podzieleniu go np. na 4, 6, 8 czy 9 części)
i znajdowanie znaku o podobnym kształcie. To pozwoliłoby lepiej oddawać
cienkie linie oraz krawędzie obiektów.
Mimo wszystko nie wygląda to najlepiej. Jednak na szczęście zamiana grupy
pikseli na pewien znak to nie jedyne, co można osiągnąć za pomocą tekstu.
Do niektórych rzeczy potrzebna jest ludzka wyobraźnia, nie wystarczy dobry
algorytm. Efekty są wtedy dużo lepsze.
Grafika
Wykorzystując kształt różnych znaków można w małym obszarze
zamknąć skomplikowany, ale całkiem czytelny obrazek:
_.-+.
_.-"" '.
+:"" '.
J \ '.
L \ _.-+
| '. _.-" |
J \ _.-" L
L +" J
+ | | -Henry Segerman-
\ | .+
\ | .-'
\ | .-'
\| .-'
+
(Prezentowane grafiki nie są mojego autorstwa, pochodzą serwisów
na temat ASCII Art) Oprócz linii, można też znaleźć sposób na rysowanie
wypełnień:
..ed$$$$$be..
.d$$$$$$$$$$$$$$c
.$$$$P"" $$$ ""*$$$$c
z$$$*" $$$ *$$$e
z$$$" $$$ ^$$$L
$$$F $$$ '$$$
4$$$ d$$$$. $$$F
4$$$ .$$$$$$$e $$$F
$$$r d$$P$$$$$$$. .$$$"
*$$$..$$$" $$$ "$$$e $$$P
*$$$$$P" $$$ ^*$$$$$$
*$$$$c. $$$ .z$$$$P
^*$$$$$$$$$$$$$$$P"
"*$$$$$$$$$*""
""""" Gilo94'
Tekst
Dzięki ASCII Art wszędzie tam, gdzie dostępny jest tylko jeden krój i
wielkość czcionki, można tworzyć duże, ozdobne napisy. Oto przykłady
napisów utworzonych w programie Email Effects:
_____ _ _ _
|_ _|__| | _____| |_ _ __ _ _| | ___ ____
| |/ _ \ |/ / __| __| | '__| | | | |/ _ \_ /
| | __/ <\__ \ |_ | | | |_| | | __// /
|_|\___|_|\_\___/\__| |_| \__,_|_|\___/___|
______ __ __ __
/_ __/__ / /_______/ /_ _______ __/ /__ ____
/ / / _ \/ //_/ ___/ __/ / ___/ / / / / _ \/_ /
/ / / __/ ,< (__ ) /_ / / / /_/ / / __/ / /_
/_/ \___/_/|_/____/\__/ /_/ \__,_/_/\___/ /___/
Linki
- Email Effects
- Bardzo dobry i wygodny program do tworzenia ASCII Art, w tym ładnych
napisów (niestety shareware)
- ASCII Generator
- Bardzo rozbudowany program do zamiany grafiki na ASCII Art (Uwaga!
Na tej stronie jest dużo wyskakujących reklam oraz próbujący się zainstalować
szpieg Gator firmy GAIN!)
- chris.com - ASCII Art Collection
- Obszerna kolekcja obrazków ASCII oraz artykuły na temat ASCII Art (szczególnie
polecam artykuł Rowana Crawforda)
- Ascii Art Dictionary
- Duża kolekcja ASCII Art
Gry tekstowe
Istnieją gry o charakterze całkowicie tekstowym. Choć z oczywistych
powodów nie są zbyt popularne, warto zainteresować się nimi. Brak
multimediów rekompensuje skomplikowany świat gry i ogromna grywalność.
Dlatego są to zazwyczaj gry typu RPG (choć ich gatunek określają specjalne
nazwy). Te gry naprawdę wciągają, wręcz uzależniają.
Inną ich cechą jest niekomercyjny charakter. Dostępne są zazwyczaj za darmo,
nierzadko razem z kodem źródłowym. Stanowią jakby alternatywny nurt wobec
komercyjnych superprodukcji.
Rougelike
Oto oryginalna definicja gatunku Rougelike pochodząca z gry ADOM:
A rogue-like game is a turnbased single-user game featuring the
exploration of a dungeon complex. You control a fictional character, often
described by race, class, attributes, skills, and equipment. This fictional
character is trying to achieve a specific goal and succeed in a difficult
quest. To fulfill the quest, you have to explore previously undiscovered
tunnels and dungeons, fight hideous monsters, uncover long forgotten
secrets, and find treasures of all kind. During the game, you explore
dungeon levels which are randomly generated each game. You might also
encounter certain special levels, which present a particular challenge or
are built around a certain theme.
The term rogue-like comes from the game Rogue. Rogue was developed in the
late 70's and released in the early 80's and is considered the mother of
all rogue-like games. Since rogue-like games have their roots in the 80's
many of the current rogue-likes still use very simple graphics or plain
ASCII characters to represent the dungeons and other locations in the game.
Rougelike to gry RPG. Gracz wciela się w postać posiadającą swoje imię,
rasę, różne współczynniki i umiejętności oraz ekwipunek (posiadane przedmioty)
i porusza się po mapie odwiedzając różne miejsca, walcząc z potworami itp.
Mapa jest złożona z kolorowych znaczków, dwuwymiarowa, pokazana w widoku od góry.
Gra jest przeznaczona dla jednego gracza i turowa w taki sposób, że wszystkie
postacie poruszają się w momencie, kiedy gracz wykonuje ruch.
Zagadnienia istotne podczas pisania gry tego rodzaju to m.in.:
- Mapa (środowisko - przyroda, a także wnętrza budynków, podziemia itp.)
- Bohater - jego cechy, współczynniki
- Inwentarz (ekwipunek) i przedmioty
- Umiejętności i magia (czary)
- NPC (Non Player Character) - potwory i inne postacie, ich sztuczna inteligencja
- Walka
- Interfejs użytkownika, obsługa, sterowanie i inne zagadnienia tzw. gameplay
- Wyświetlanie (grafika)
- LOS (Line Of Sight) - pokazywanie tylko tych potworów, które są w zasięgu
widzenia bohatera z uwzględnieniem zasłaniania przez różne obiekty
Ponadto w grach Rougelike wiele (o ile nie wszystko) generowane jest przez
algorytmy, a nie zapisane w utworzonych wcześniej plikach. Generowany
może być teren, budynki, rozmieszczenie potworów, a nawet imiona postaci.
Algorytmy generowania powinny posiadać element losowy i dawać dobre efekty.
Oto zrzut ekranu z gry ADOM uruchomionej na konsoli:
Zobacz obrazek
Linki
- Dungeondweller (roguelikedevelopment.org)
- Serwis w całości poświęcony tworzeniu gier Rougelike, zawiera obszerny
zbiór artykułów na ten temat
- ADOM - Ancient Domains Of Mystery
- Jedna z najbardziej znanych gier Rougelike
- Serwis ADOM
- Polska strona poświęcona grze ADOM
- The Official Angband Home Page
- Angband - inna gra Rougelike
MUD
MUD (Multi User Dungeon) to sieciowa gra tekstowa całkowicie pozbawiona widoku mapy.
Gracz czyta jedynie opisy miejsc, między którymi przechodzi, obiektów, którym chce
się przyjrzeć oraz postaci, które spotyka. Porusza się i wszelkie inne czynności
wykonuje za pomocą specjalnych poleceń.
Charakterystyczne dla gier MUD jest to, że działają one wyłącznie przez sieć.
Nie są to jednak gry typu host-join, gdzie jeden gracz zakłada grę, kilku innych
dołącza się i odbywa się rozgrywka. Każdy MUD ma jeden wielki świat gry, całkowicie
liczony na serwerze i gracze przyłączając się do niego grają w nim wspólnie.
Podobnie jak Rougelike, są to gry RPG osadzone zazwyczaj w świecie fantasy.
Gracze sterują swoimi postaciami, zdobywają coraz wyższe współczynniki i coraz
lepsze przedmioty, a także walczą z potworami i ze sobą nawzajem. Mogą też oczywiście
rozmawiać i robić wiele różnych innych rzeczy.
Wygląda na to, ze dopiero obecnie komercyjni producenci "multimedialnych" gier
zaczynają dostrzegać zalety płynące z takiego podejścia do gier sieciowych. Owocuje to
powstawaniem wielu gier określanych jako MMORPG (Massive Multiplayer Online Role
Playing Game). Dla nich jednak to okazja, by wprowadzić opłaty abonamentowe za
korzystanie z serwera. Tymczasem w MUDy można grać za darmo i najczęściej wystarczy
do tego dowolny klient Telnet - nie trzeba nawet uruchamiać żadnego osobnego programu!
Linki
- Argadia
- Cygnus Division
- LAC MUD
- Kuźnia Dusz
- Polskie gry MUD
- Smaug - Mud Design
- Silnik do tworzenia własnych gier MUD
Otchłań
Otchłań to gra tekstowa bez widoku mapy podobna do gier MUD.
W odróżnieniu od nich jednak ta w pełni polska produkcja działa jako osobna
aplikacja i przeznaczona jest do gry lokalnej - dla jednego gracza.
Oto zrzut ekranu z tej gry:
Zobacz obrazek
Linki
- Strona domowa Otchłani
- Oficjalna strona gry
- Świat Otchłani
- Fajna strona o Otchłani (aktualnie nie działa)
- Imperium Otchłani
- Otchłań PageZ by Cet
- Inne strony poświęcone tej grze
Język naturalny
Oprócz poleceń formułowanych dla komputera i komunikatów otrzymywanych
od niego, komputer może też w pewien sposób obsługiwać tekst pisany
w języku naturalnym (np. polskim czy angielskim) - choćby tylko go
przesyłać.
Komunikacja
Komunikacja międzyludzka jest jednym z zastosowań tekstu. Taki sposób
wykorzystania Internetu był jednym z pierwszych i nadal pozostaje jednym
z podstawowych - mimo wielu pojawiających się niedogodności, jak coraz
większa plaga spamu.
Jest to o tyle ważne, że cyfrowemu medium przesyłania informacji daleko
jeszcze do wygody, z jaką używa się tradycyjnego telefonu. Podejmowane są
jednak próby zapewnienia wygodnej komunikacji głosowej, jak darmowy, głosowy
komunikator P2P - Skype.
Komunikację za pomocą tekstu można podzielić na:
- Synchroniczną
- Rozmowa odbywa się w czasie rzeczywistym poprzez wymianę krótkich
wypowiedzi, np.: IRC, Instant Messaging (komunikatory, jak Gadu-Gadu),
chaty przez WWW
- Asynchroniczną
- Na serwerze zapisywane są dłuższe wiadomości tekstowe i inne osoby
mogą je później czytać, np.: e-mail, grupy dyskusyjne, fora przez WWW
Komunikacja tekstowa przez Internet spowodowała wykształcenie
charakterystycznego języka, zestawu skrótów, symboli i innych zasad.
Np. często nie używa się polskich liter, a czasami nawet dużych liter i
interpunkcji. W powszechnym użyciu są za to uśmieszki (emotikonki).
Ta sieciowa "nowomowa" bywa przez niektórych potępiana. Nie rozumieją
oni, że tekst tego rodzaju ma pełnić taką rolę, jak głos w czasie zwykłych
rozmów, a nie jak słowo pisane w książkach czy artykułach.
Warto przy okazji wspomnieć o botach. Boty, szczególnie powszechne na
IRCu, to programy działające na takich samych zasadach jak zwykli
użytkownicy - siedzą na danych kanałach, mają swoją ksywę itd. Spełniają
zawsze określone funkcje, np. pilnują kanału i porządku na nim albo
świadczą użytkownikom pewne usługi.
Linki
- Eggheads.org
- Eggdrop - najpopularniejszy, uniwersalny bot IRC
- Skype
- Darmowy, głosowy komunikator P2P, który "po prostu działa"
Chatterboty
<AnA> CZESC
<Regedit> JAK SIĘ NAZYWASZ?
<AnA> JA NAZYWAM SIE ANA
<Regedit> A ILE MASZ LAT?
<AnA> O JESTEM MLODA MAM 22 LATA
To nie początek podrywu na IRC, ale krótki fragment rozmowy z programem.
Chatterboty to aplikacje sztucznej inteligencji, których zadaniem jest
rozmowa z człowiekiem za pomocą tekstu. AnA jest jedną z nich.
Zadanie napisania programu, który potrafiłby prowadzić inteligentną
konwersację wydaje się niemożliwe i póki co, faktycznie takie jest. Już
niejeden program próbował zaliczyć tzw. test Turinga i jak na razie żadnemu
się nie udało. Zadanie polega na tym, aby rozmówca nie był w stanie
stwierdzić, że rozmawia z komputerem a nie z człowiekiem.
Nie chodzi jednak o to, by stworzyć sztucznego człowieka. Chatterbot
to pewna forma komunikacji człowieka z maszyną. W obecnym stanie pełni
raczej rolę ciekawostki. Boty tworzone są zwykle przez pasjonatów i służą
jedynie rozrywce.
Jednak przewiduje się ich zastosowania np. w roli cyfrowego
przedstawiciela firmy. Łatwiej będzie klientowi odwiedzającemu stronę WWW
po prostu spytać o coś bota, niż szukać informacji po rozbudowanym
serwisie.
Przykładem takiego bota jest Fido. Pod względem technicznym wydaje się
dość prymitywny. Oprócz opowiadania o sobie i swojej firmie
potrafi pokazywać dowcipy ze swojej bazy, a podczas pożegnania prosi o
podanie adresu e-mail (ciekawe po co? :P).
Jak działa chatterbot? Możliwości jego budowy jest bardzo wiele - od
najprostszych po bardzo skomplikowane. Różnią się one uzyskiwanymi
efektami, jednak żadne nie pozwalają choćby zbliżyć się do poziomu
reprezentowanego przez człowieka. Oto garść możliwych rozwiązań:
- Rozpoznawanie słów kluczowych na wejściu i w reakcji na nie
wypisywanie na wyjście jednej z predefiniowanych odpowiedzi.
- Rozpoznawanie rodzaju wypowiedzi (czy to jest pytanie) poprzez
znajdowanie znaku "?" oraz słów takich jak "czy", "kto", "ile" itp.
- Rozpoznawanie emocji wyrażonych w wypowiedzi, np. poprzez znajdowanie
wykrzykników i uśmieszków.
- Próba rozpoznania, co jest aktualnym tematem dyskusji (podmiotem).
- Uwzględnianie także poprzednich wypowiedzi, a nie tylko ostatniego
pytania (kontekst).
- Zadawanie pytań, a nie także udzielanie odpowiedzi. Podtrzymywanie
rozmowy.
- Stosowanie różnych trików psychologicznych i odpowiedzi wymijających,
ogólnych.
Wiara w to, że zastosowanie modnych technik, jak sieci
neuronowe czy algorytmy genetyczne spowoduje niespodziewanie, że komputer
zacznie myśleć, jest naiwna. W praktyce lepiej sprawdzają się chyba
rozwiązania tradycyjne oraz solidne, skomplikowane algorytmy, ewentualnie
systemy ekspertowe.
Ciekawym pomysłem byłoby uznanie, że bot nigdy nie dorówna człowiekowi
i napisanie go w taki sposób, aby mógł być traktowany jako "niższa forma
życia". Użytkownikom mógłby się taki program spodobać, ponieważ
dostarczałby rozrywki i sympatia do niego oparta byłaby na tych samych
ludzkich instynktach, dzięki którym lubimy hodować psy, chomiki i inne
zwierzątka.
Jeśli chodzi o dane przechowywane przez bota, może to być np. baza słów
kluczowych i odpowiedzi lub ich fragmentów. Ogólna zasada jest taka, że im
bardziej próbuje się stworzyć bota inteligentnego (samodzielnie generującego
odpowiedzi z małych fragmentów, uczącego się), tym mniej sensowne i składne są
jego wypowiedzi.
Istota problemu jest oczywista. Chatterbot działa w taki sposób, w jaki
działałby np. człowiek nauczony reagować wg pewnego algorytmu na pewne
wyrazy jakiegoś języka nie znając go i nie rozumiejąc, o czym mówi.
Aby napisać chatterbota potrafiącego zdać test Turinga, trzebaby chyba
zaimplementować takie składniki:
- Analizę otrzymywanych wypowiedzi i odwrotnie - składanie swoich
odpowiedzi z poszczególnych wyrazów. Takie teksty reprezentowane byłyby
w pamięci w postaci drzewa, tak jak wygląda rozkład gramatyczny zdania,
którego uczą w szkole podstawowej. Bot musiałby znać wszystkie wyrazy
i ich formy gramatyczne, co jest szczególnie trudne w przypadku języka
polskiego.
- Rozumienie wypowiedzi i wnioskowanie - bot musiałby oprócz
umiejętności posługiwania się językiem także posiadać informacje
o świecie lub pewnej dziedzinie wiedzy i prawidłowo z nich korzystać -
czyli po prostu myśleć!
Jednak nawet implementując te możliwości pozostałby szereg
problemów:
- Nierozumienie wypowiedzi niekompletnych czy zawierających błędy
(chociażby literówki)
- Powinien posiadać własne opinie i poglądy
- Powinien posiadać emocje
- Powinien posiadać poczucie humoru
- Powinien posiadać poczucie czasu i miejsca oraz zbierać informacje
na temat różnych obiektów i osób
Mimo tego chatterboty pozostają przedmiotem zainteresowania wszystkich
- od programistów-pasjonatów, poprzez firmy, aż po ośrodki naukowe.
- AnA wirtualna kobieta
- Polski chatterbot
- The A.L.I.C.E. Artifical Intelligence Foundation
- Chatterbot rozmawiający po angielsku - bardzo poważny projekt
- fido interactive
- Firma zajmująca się komercyjnym zastosowaniem chatterbotów i jej bot - Fido
Tłumaczenie tekstu
Innym zagadnieniem związanym z cyfrowym przetwarzaniem języka
naturalnego jest tworzenie programów tłumaczących całe teksty pomiędzy
różnymi językami. Programów takich powstaje wiele i są one coraz lepsze.
Jednak nadal jakość uzyskiwanych tekstów pozostawia wiele
do życzenia, a programy tego typu nie mogą zastąpić żywych tłumaczy.
Oto przykład tłumaczenia pierwszych zdań polskiej wersji licencji GNU
GPL za pomocą programu Komputerowy Tłumacz Języka Angielskiego
firmy Kompas:
Tekst po polsku:
Większość licencji na oprogramowanie pomyślana jest po to, aby odebrać
użytkownikowi możliwość swobodnego udostępniania innym i zmieniania danego
software'u. Natomiast w wypadku Powszechnej Licencji Publicznej GNU (GNU
General Public License, GPL) celem jest zagwarantowanie użytkownikowi
swobody udostępniania i zmieniania tego wolnego oprogramowania, a więc
danie pewności, iż oprogramowanie jest wolno dostępne dla wszystkich
użytkowników.
Przekład na angielski:
The most of the licence on the software conceived is after this , to take
the user the possibility of free throwing open with other and changings of
the given software'at. Instead in the event of of the General Public
Licence THE GNOO (THE GNOO General Public License , GPL) an aim {target}
is the guarantee to the user of the freedom of throwing open and changings
of this free software , and so the giving {course} of the certainty ,
that the software is slowly accessible for all users.
Przekład z powrotem na polski:
Najbardziej z pozwolenia {licencji} na oprogramowaniu poczęty jest w pogoni
za {jest po} tym , by brać użytkownikowi możliwość wolny rzucającego
otwartego z innym i changings danego oprogramowania'przy. Zamiast tego
w wypadku Ogólnego Publicznego Pozwolenia {Licencji} GNU (GNU Ogólne
Publiczne Pozwolenie , GPL) cel {celu} jest gwarancja {gwarant} do
użytkownika wolności rzucania otwartego i changings tego oprogramowania
darmowego , i tak dający {bieg {kurs}} pewności , że oprogramowanie
jest powoli dostępne dla wszystkich użytkowników.
Najprostszym podejściem do zadania jest bezpośrednie tłumaczenie
wyrazów za pomocą słownika. Pojawia się jednak szereg problemów:
- Jeden wyraz ma kilka znaczeń - należałoby wybrać odpowiednie
na podstawie kontekstu
- Należałoby uwzględnić terminologię specjalistyczną, np. w informatyce
"driver" znaczy "sterownik", a nie "kierowca"
- W różnych językach (szczególnie tak różnych, jak polski i angielski)
obowiązuje różny szyk zdania
- Nie wiadomo, czy dany zwrot nie jest nazwą własną - żeby np. Red Hat
nie został "czerwonym kapeluszem" :)
- W języku polskim wyrazy posiadają różne formy i odmiany - bez uch
uwzględnienia wychodzi "Kali zjeść słonia" :)
Moim zdaniem, rozwiązaniem idealnym byłoby utworzenie uniwersalnego
formatu reprezentującego pojęcia i ich powiązania, niezależnego od żadnego
języka. Gdyby udało się przetwarzać różne języki na ten format w obydwie
strony, raz na zawsze zniknęłaby bariera językowa, a stałoby się to bez
uszczerbku na bogactwie różnych języków świata. Pomogłoby też znacznie
w tworzeniu chatterbotów.
Rozwój informatyki, a także wzrost szybkości komputerów i rozmiaru
pamięci już nie raz pozwolił na pokonanie różnych ograniczeń i tym samym
napisanie rzeczy wcześniej niemożliwych. Dlatego wierzę, że kiedyś także
w sprawie języka naturalnego komputery dużo nam pomogą...
Ciekawostka
Postaraj się przeczytać poniższy tekst z normalną szybkością i zrozumieć
go - tak jak się normalnie czyta - nie skupiając się na poszczególnych
literach:
Zdognie z nanjwoymszi baniadmai perzporawdzomyni na bytyrijskch
uweniretasytch nie ma zenacznia kojnoleść ltier przy zpiasie dengao sołwa.
Nwajżanszjie jset, aby prieszwa i otatsnia ltiera błya na siwom mijsecu,
ptzosałoe mgoą być w nieaedziłe i w dszalym cąigu nie pwinono to sawrztać
polbemórw ze zozumierniem tksetu. Dzijee się tak datgelo, że nie czamyty
wyszistkch lteir w wazyrie, ale cłae sołwa od razu. Młeigo dina.
Czyżby pojawiła się nowa koncepcja stratnej kompresji tekstu? :)))
Wyszukiwanie
W wielu zastosowaniach zachodzi potrzeba przeszukiwania tekstu. W
najprostszym przypadku polega ono na stwierdzeniu obecności bądź
nieobecności danego wyrazu w danym tekście. Jednak temat jest dużo bardziej
obszerny i złożony.
Wyszukiwać można np. pliki na dysku. Każdy edytor tekstu ma funkcję
"Znajdź i zamień...". Wyszukiwarki internetowe, z których korzystamy na co
dzień, także dokonują przeszukiwania tekstu.
Wildcards
Wildcards (symbole wieloznaczne) to wyszukiwanie tylko o krok bardziej
złożone, niż zwykłe poszukiwanie podanego tekstu. Znamy je wszyscy
doskonale - służy nam bowiem do wyszukiwania plików już od czasów systemu
DOS. *.exe to właśnie wildcards.
Zasada działania polega na sprawdzaniu, czy podany tekst (lub jego
fragment) pasuje do podanej maski. Maską jest łańcuch, którego znaki
interpretowane są dosłownie i porównywane ze znakami przeszukiwanego
tekstu za wyjątkiem znaków specjalnych zwanych symbolami
wieloznacznymi:
- ? - oznacza jeden, dowolny znak
- * - oznacza dowolną ilość (także 0) dowolnych znaków
Oto przykłady masek i pasujących do nich łańcuchów:
? a
X
??a* XXa
12aBLEBLEBLE
*.* .
coś1.
coś1.coś2
p*e pe
programowanie
pie______e
Zaprezentuję teraz przykładową implementację funkcji w C++, która
sprawdza, czy podany łańcuch jako całość pasuje do podanej maski:
bool ValidateWildcard(const std::string &mask, const std::string &s,
bool CaseSensitivity)
{
size_t j;
size_t maskl = mask.size();
size_t sl = s.size();
// dla każdego znaku maski...
for (size_t i = 0; i < maskl; ++i)
{
// rekurencja
if (mask[i] == '*')
{
for (j = i; j < sl+1; ++j)
if (ValidateWildcard(mask.substr(i+1, maskl-1), s.substr(j,
sl-j+1),
CaseSensitivity))
return true;
return false;
}
// jeśli znak maski wykracza poza znak łańcucha - false
else if (i >= sl)
return false;
// jeśli znaki łańcucha wykraczają poza maskę - false
else if ( (i == maskl-1) && (sl > maskl) )
return false;
// porównanie znaków
// - '?' - znak w stringu może być dowolny - można olać sprawę :)
else if (mask[i] == '?')
{
// Nic
}
// - inny znak - musi się zgadzać ze znakiem łańcucha
else if (
( (mask[i] != s[i]) && CaseSensitivity ) ||
( CharUpper((char*)mask[i]) != (CharUpper((char*)s[i])) &&
!CaseSensitivity)
)
return false;
}
return true;
}
Jako symbole wieloznaczne mogą być używane inne znaki, np. w SQL
pojedynczy znak zastępuje podkreślenie "_", a dowolny ciąg znaków procent
"%".
Wyrażenia regularne
Wyrażenie regularne (ang. "regular expression" - w skrócie "regexp") to
sposób przeszukiwania tekstu bardziej zaawansowany, niż wildcards. Działa
na podobnej zasadzie, ale pozwala używać bardzo wielu różnych znaków
o specjalnym znaczeniu. Przeszukiwany łańcuch jest lub jego fragment jest
dopasowywany do podanego wyrażenia zwanego też wzorem (ang. "pattern").
Oprócz przeszukiwania można dzięki nim wybierać pewne elementy z wnętrza
łańcucha (parsować go), dokonywać jego dzielenia na części, zastępować pewne
fragmenty innymi itp. Wyrażenia regularne są bardzo potężne.
Osobie nieznającej ich składni się jednak wydawać przerażające, np.:
/(<([\w]+)[^>]*>)(.*)(<\/\\2>)/
Jak się jednak już zaraz okaże, ich składni można się bardzo szybko
nauczyć.
Istnieją implementacje kilku standardów wyrażeń regularnych. Jedną z nich
jest biblioteka PCRE rozprowadzana na licencji Open Source, której autorem
jest Philip Hazel. Implementuje ona standard używany w języku Perl, a także
w PHP. Inną bibliotekę napisał Henry Spencer. Jest ona nastawiona na
zgodność ze standardem POSIX 1003.2 i używana m.in. w MySQL, TCL, a także
w PHP.
Podstawowe zasady i najważniejsze używane znaki specjalne są w każdym
z tych standardów podobne. W Internecie znajdziesz wiele opisów składni
wyrażeń regularnych. Są dołączane praktycznie do każdego oprogramowania, które
ich używa. Dlatego opiszę tylko niektóre jej elementy.
Wyrażenia regularne obejmuje się w ukośniki "/ ... /". To dość egzotyczna
odmiana nawiasu :)
Istnieje szereg modyfikatorów stosowanych w celu zmiany standardowego
zachowania parsera wyrażeń regularnych, np. nakazanie mu, by nie rozróżniał
wielkości liter.
Najprostsze wyrażenie nie zawiera żadnych znaków specjalnych. Np.
wyrażenie "hello" pasuje tylko do łańcucha "hello" i do żadnego innego.
Każda litera takiego wyrażenia jest tzw. atomem.
Po każdym atomie może wystąpić specjalny znak określający dopuszczalną
ilość jego powtórzeń:
- brak
- dokładnie jedno
- ?
- zero lub jedno
- +
- jedno lub więcej
- *
- zero lub więcej
- {m}
- dokładnie m
- {m,}
- m lub więcej
- {m,n}
- co najmniej m i co najwyżej n
Oto przykład wyrażeń i pasujących do nich łańcuchów:
xAy xA?y xA+y xA*y xA{3}y
------------------------------------------
xy X X
xAy X X X X
xAAAy X X X
Odwrócony ukośnik służy do poprzedzania innych znaków i nadaje im
specjalne znaczenie:
- \X
- dosłowne potraktowanie znaku X (może to być dowolny znak) - nie
jako znak specjalny
- \r, \n, \t itp.
- tak jak w C++ i wielu innych językach; tu
odpowiednio: znak powrotu karetki, końca wiersza i poziomej
tabulacji
- \DDD, \xHH
- znak o kodzie DDD zapisanym dziesiętnie lub HH zapisanym
szesnastkowo
Atomem może być też taki element, który pasuje do kilku różnych
znaków:
- [az]
- Pasuje do niego litera "a" lub "z"
- [a-z]
- Pasuje do niego każda litera pomiędzy "a" i "z" włącznie
- [^az]
- Pasuje do niego każdy znak z wyjątkiem litery "a" i "z"
Istnieją też predefiniowane znaki specjalne określające pewne grupy
znaków, np.:
- \d
- Każda cyfra dziesiętna
- \D
- Każdy znak, który nie jest cyfrą dziesiętną
- \s
- Każdy biały znak
- \S
- Każdy znak, który nie jest biały
Osobno wymienić trzeba dwa specjalne znaki:
- ^
- Oznacza, że w tym miejscu musi być początek łańcucha
- $
- Oznacza, że w tym miejscu musi być koniec łańcucha
Oczywiście różne elementy składni wyrażeń regularnych można ze sobą
łączyć. Na przykład wzór:
^p[^a-dX]+e$
Pasuje do każdego łańcucha, który rozpoczyna się od litery "p", kończy
się literą "e", a pomiędzy nimi ma co najmniej jeden znak. Przy tym
wszystkie znaki pomiędzy nimi muszą być różne od "a", "b", "c", "d" i
"X".
Kropka zastępuje dowolny znak. Pionowa kreska "|" służy do oddzielania
kilku alternatywnych łańcuchów, np. do wzoru:
pl|en
pasuje łańcuch "pl", jak również łańcuch "en".
Asercja to specjalny element, który nie powoduje odczytania nowego
znaku, a jedynie warunkuje wystąpienie w danym miejscu określonej
sytuacji, np.:
- \b
- W tym miejscu musi być granica słowa
- \B
- W tym miejscu nie może być granicy słowa
Na koniec trzeba wspomnieć o zwykłych nawiasach, które służą do
tworzenia podwyrażeń. Łańcuch dopasowany do takiego podwyrażenia zostanie
zwrócony jako jeden z wyników przetwarzania wyrażenia regularnego (może być
więcej takich podwyrażeń).
Aby utworzyć podwyrażenie (np. w celu użycia kilku alternatywnych
łańcuchów oddzielonych pionową kreską "|"), a nie spowodować przy tym
zwrócenia jego treści, użyj takiego nawiasu:
(?: ... )
Na zakończenie pozwolę sobie przytoczyć przykład zaczerpnięty
z podręcznika PHP pokazujący zastosowanie pokazanego na początku tego
podrozdziału wyrażenia regularnego. Poniższy kod parsuje przekazany
łańcuch w postaci kodu HTML na zbiór znaczników. Każdy z rezultatów
składa się z rozpoczęcia, treści i zakończenia.
$html = "<b>bold text</b><a href=howdy.html>click me</a>";
preg_match_all("/(<([\w]+)[^>]*>)(.*)(<\/\\2>)/", $html, $matches);
for ($i=0; $i < count($matches[0]); $i++) {
echo "matched: " . $matches[0][$i] . "\n";
echo "part 1: " . $matches[1][$i] . "\n";
echo "part 2: " . $matches[3][$i] . "\n";
echo "part 3: " . $matches[4][$i] . "\n\n";
}
A oto wynik jego działania:
matched: <b>bold text</b>
part 1: <b>
part 2: bold text
part 3: </b>
matched: <a href=howdy.html>click me</a>
part 1: <a href=howdy.html>
part 2: click me
part 3: </a>
Linki
- PCRE
-
- Biblioteka implementująca standard Perla
Przeszukiwanie tekstu
Temat przeszukiwania tekstu to nie tylko sprawdzanie zgodności łańcucha
z podanym wzorcem. Spróbujmy sobie wyobrazić, jak działa wyszukiwarka
internetowa. Musi posiadać bazę zapisanych w jakiejś postaci informacji
o znanych stronach WWW, wydajnie ją przeszukiwać, a użytkownikowi
udostępniać możliwość wygodnego zadawania zapytań i czytelnie prezentować
wyniki.
Słowa kluczowe
Najprostszym rozwiązaniem katalogowania dużej ilości zasobów jest
przypisywanie każdemu z nich zbioru słów kluczowych. Np. pewna książka
w bibliotece może mieć słowa kluczowe:
C++,programowanie,język
Użytkownik miałby możliwość wyszukiwania książek, w których występują
podane przez niego słowa kluczowe.
Wyrażenia logiczne
Ważny jest sposób zadawania zapytań. Dawniej bardzo powszechne były
wyrażenia używające spójników logicznych, np. wyrażenie:
programowanie AND ("C++" OR Pascal) AND NOT Basic
spowodowałoby wyszukiwanie wszystkich tych pozycji na temat
programowania, które traktują o języku C++ lub Pascal, ale w których nie
ma ani słowa o języku Basic.
Częściej spotykane spójniki to:
- x AND y
- i
- x OR y
- lub
- NOT x
- nie
- x NEAR y
- obok, w pobliżu
- +x
- podany wyraz musi wystąpić
- -x
- podany wyraz nie może wystąpić
Ponadto można używać cudzysłowów do obejmowania łańcuchów zawierających
dowolne znaki i odstępy, żeby zostały potraktowane dosłownie. Można też
ustalać kolejność wykonywania działań za pomocą nawiasów.
Nowoczesne wyszukiwanie
Wydaje się, że obecnie panuje tendencja, by odchodzić od tych niezbyt
przystępnych wyrażeń logicznych. Zamiast nich, daje się użytkownikowi
możliwość wpisania listy wyrazów do wyszukania - jeden za drugim.
Ewentualnie można je obejmować w cudzysłowy.
Cały problem polega wtedy na tym, by odpowiednio skonstruować listę
wyników wyszukiwania - zwłaszcza właściwie posortować jej pozycje
względem pewnego współczynnika - trafności. Użytkownicy nie mają zwyczaju
zaglądania na dalsze strony listy z wynikami i sedno sprawy powinni mieć
od razu na pierwszym miejscu.
Chyba właśnie to zdecydowało o sukcesie wyszukiwarki Google. Po wpisaniu
nazwy jakiegoś programu na pierwszym miejscu dostajemy link do jego strony
głównej, a po wpisaniu jakiegoś ogólnego tematu - linki do największych
poświęconych mu serwisów. Inne wyszukiwarki mają zwyczaj prezentować w tym
miejscu szereg bezużytecznych stron, w których przypadkiem wystąpiło
szukane słowo.
Powstaje pytanie, w jaki sposób szacować trafność znalezionych stron?
Poniżej prezentuję przykładową funkcję dokonującą wyszukiwania łańcucha
podanego jako pierwszy parametr w łańcuchu podanym jako drugi parametr.
Funkcja zwraca liczbę zmiennoprzecinkową oznaczającą "trafność". Będzie
to 0, jeśli szukane wyrażenie nie zostało znalezione lub liczba dodatnia,
jeśli zostało znalezione. Jak duża będzie to liczba? To zależy... Zwykle
ok. 1-10.
Mówiąc ogólnie, zwrócona trafność jest tym większa, im:
- Poszukiwane wyrażenie jest dłuższe
- Przeszukiwany tekst jest krótszy
- Poszukiwane wyrażenie zostanie znalezione więcej razy
- Znalezione wyrażenie ma taką samą wielość liter, jak poszukiwane
- Znalezione wyrażenie jest całym ciągiem tzn. np. "Fajna GRA
strategiczna", a nie "proGRAmowanie"
- Wyrażenie znalezione zostanie na początku przeszukiwanego tekstu
- Wyszukiwane wyrażenie stanowi dokładnie treść przeszukiwanego
tekstu
// Funkcja do użytku wewnętrznego dla FineSearch
// Zwraca liczbę zależną od okoliczności, w jakich występuje
// znaleziony string.
// Mnożona jest przez nią obliczana trafność.
float _MnoznikOkolicznosci(const std::string &str, size_t start,
size_t length)
{
bool l = (start == 0);
bool r = (start+length == str.size());
// Całe pole
if (l && r)
return 4.0f;
// Początek pola
else if (l)
return 3.0f;
else
{
// if (!l)
if (IsCharAlphaNumeric(str[start-1]))
l = true;
if (!r)
if (IsCharAlphaNumeric(str[start+length]))
r = true;
// Cały ciąg
if (l && r)
return 2.0f;
// Nic ciekawego
else
return 1.0f;
}
}
float FineSearch(const std::string &asubstr, const std::string &astr)
{
std::string substr = asubstr;
std::string str = astr;
std::string usubstr = LowerCase(substr);
std::string ustr = LowerCase(str);
float result = 0.0f;
size_t p;
float x;
while (true)
{
p = ustr.find(usubstr);
// Koniec szukania
if (p == std::string::npos)
break;
x = max( usubstr.size()/5.0f - astr.size()/100.0f + 1.0f, 1.0f);
// Jeśli zgadza się wielkość liter
if (str.substr(p, substr.size()) == substr)
x *= 1.5;
// Mnożnik okoliczności - jeśli to całe pole,
// początek pola lub cały ciąg
x *= _MnoznikOkolicznosci(astr, p+astr.size()-str.size(),
substr.size());
// Usuwamy co przerobione i od nowa :)
str = str.substr(p+substr.size());
ustr = ustr.substr(p+substr.size());
// No i oczywiście dodajemy wyliczoną trafność
result += x;
}
return result;
}
Funkcję wyszukującą trzeba wywołać wiele razy, by każde pole każdego
rekordu przeszukać w poszukiwaniu każdego z wyrażeń wpisanych w zapytaniu
przez użytkownika. Otrzymaną trafność należy dla każdego rekordu
sumować.
Oto przykład użycia. Zakładamy, że funkcja ma za zadanie przeszukać
pojedynczy rekord danych. Składa się on z dwóch pól nazwanych Pole1 i
Pole2. Query to jakiś obiekt przechowujący listę wyrazów do wyszukania.
float trafnosc = 0;
for (int i = 0; i < Query.Count-1; ++i)
{
trafnosc = trafnosc + 2.0f * FineSearch(Query[i], Pole1);
trafnosc = trafnosc + 1.0f * FineSearch(Query[i], Pole2);
}
Jak widać, obydwa pola rekordu przeszukiwane są w poszukiwaniu każdego
z wyrażeń zapytania (Query). Trafność jest sumowana.
Poszczególne pola mogą mieć różne znaczenie, dlatego warto nadawać im
współczynniki wagowe. Zakładamy, że Pole1 to nazwa (tytuł - a więc ważny)
rekordu, a Pole2 to jakaś tam jego treść (czyli mniej ważna). Jak widać
na powyższym przykładzie, polu pierwszemu nadajemy wagę 2 razy większą,
niż drugiemu.
Wyszukane rekordy powinny być sortowane wg trafności. Nie ma jakiegoś
maksymalnego limitu trafności. Jeśli chcesz, możesz już po zakończeniu
wyszukiwania przeliczyć je na procenty przeskalowując ich wartość tak, by
rekord o największej trafności otrzymał 100, a pozostałe proporcjonalnie
mniej.
Jeśli przeszukujesz jakąś strukturę hierarchiczną, np. system plików i
chcesz, aby wyszukiwanie było jeszcze "fajniejsze", możesz zsumowaną już
trafność modyfikować w zależności od poziomu zagłębienia danego rekordu.
Przykładowo możesz dzielić trafność przez liczbę poziomów zagłębienia
podzieloną przez dwa.
trafnosc = trafnosc / (level/2);
Trafność Rekordu na najwyższym (pierwszym) poziomie podzielona zostanie
przez 0.5, czyli pomnożona przez 2. Trafność rekordu na poziomie drugim
zostanie podzielona przez 1, czyli pozostanie bez zmian. Na poziomie
trzecim podzielona zostanie przez 1.5, na czwartym zmniejszy się
dwukrotnie itd.
Jak jeszcze można wzbogacić ten algorytm? Najlepiej byłoby dysponować
jakąś liczbą określającą ogólną "wartość" danego rekordu. Można byłoby
po prostu pomnożyć przez nią otrzymaną trafność. Może to być np.
popularność poszczególnych stron znana choćby z częstości klikania na linki
do nich, kiedy pojawiają się w wynikach wyszukiwania twojej
wyszukiwarki.
Jest jeszcze jedna kwestia, która pozostaje nierozwiązana. Algorytm
mógłby rozpoznawać także wyrazy podobne do szukanych (np. z jedną literą
dodatkową, brakującą czy zmienioną), a nie tylko identyczne. Wymagałoby to
ułożenia algorytmu oceniającego podobieństwo dwóch wyrazów.
Języki opisu
W formacie tekstowym można przechowywać ustrukturalizowane informacje.
Służą do tego specjalnie stworzone tekstowe formaty (lub inaczej języki
opisu), jak HTML czy XML. Każdy taki język ma swoje zastosowania. Jedne
przeznaczone są do konkretnych celów (jak HTML do tworzenia stron WWW).
Inne z kolei są uniwersalne i pozwalają tworzyć własne formaty
do przechowywania różnego rodzaju informacji.
Przechowywanie danych w formacie tekstowym ma zarówno wady, jak i
zalety. Do wad zaliczyć można na pewno większą objętość danych i większą
czasochłonność ich analizy przez komputer, niż miałoby to miejsce
w przypadku formatu binarnego. Istnieje jednakże jedna wielka zaleta takich
języków - są one tak równie czytelne dla człowieka, co dla maszyny!
(czasami równie mało czytelne :)
Jaki musi być tekstowy język opisu? Z pewnością musi posiadać w pełni
zdefiniowaną i ściśle określoną składnię. Nie może być żadnych
wieloznaczności. Z drugiej strony powinien dopuszczać pewną swobodę
w zapisie, aby człowiek piszący taki plik mógł samemu ustalać układ
danych.
XML
Istotę i sens tekstowych języków opisu postaram się wyjaśnić
na przykładzie języka XML. Znajomość podstaw jego składni z pewnością
przyda się niejednokrotnie.
Czym jest XML? Trudno precyzyjnie odpowiedzieć na to pytanie. W zasadzie
jest to standard stworzony przez konsorcjum W3C. Znającym język HTML
znajome wydadzą się niektóre reguły tego języka. Jednak XML to nie jest
z góry określony język. To raczej zbiór reguł, dzięki którym można
definiować własne języki.
Wyobraź sobie, że piszesz grę, a do zapisywania rodzajów potworów,
jakie w niej wsytępują, używasz XMLa. Przykładowy plik mógłby wyglądać
tak:
<?xml version="1.0" encoding="UTF-16" standalone="yes"?>
<potwory>
<potwór nazwa="Szkielet" obrażenia="10" życie="10"/>
<potwór nazwa="Zombi" obrażenia="25" życie="16"/>
</potwory>
Dzięki temu nie musiałbyś pisać edytora. Spis potworów mógłbyś stworzyć
po prostu w systemowym notatniku lub dowolnym innym edytorze tekstu
niesformatowanego. Dopuszczalne nazwy i wzajemny układ elementów (tutaj
"potwory" i "potwór"), ich atrybuty (tutaj "nazwa", "obrażenia" i
"życie") oraz ogolną strukturę dokumentu definiujesz ty sam, w zależności
od potrzeby.
XML to jednak nie tylko nowy format pliku, w pewnym sensie alternatywny
względem plików binarnych czy własnych formatów tekstowych. To także pewna
idea. W założeniu dokument XML ma przechowywać czyste dane, bez informacji
o ich formatowaniu. Inaczej mówiąc - samą treść, a nie formę. Coraz więcej
programów wspiera XML. Wydaje się, że właśnie on stanowi przyszłość
przechowywania, przesyłania i przetwarzania danych, szczególnie
w Internecie.
Przejdźmy teraz do opisu języka XML. Jest to skrót od "Extensible
Markup Language", czyli "rozszerzalny język znaczników". Dokument składa
się z różnego rodzaju informacji i zbudowany jest w sposób hierarchiczny.
Podstawowym rodzajem informacji są elementy, podobnie jak w języku HTML.
Mogą być zagnieżdżane jedne w drugich. Jednakże, inaczej niż w HTML, każdy
element musi posiadać zamknięcie, a zamknięcia nie mogą się krzyżować.
Innymi słowy, element może zawierać w swoim wnętrzu kolejne elementy oraz
inne informacje.
Prawidłowy dokument XML rozpoczyna się prologiem. Dalej następuje
pojedynczy element główny, który zawiera w swoim wnętrzu wszystkie
informacje, jakie dokument ma przechowywać.
Element (inaczej znacznik - ang. "tag") może składać się z rozpoczęcia,
zawartości i zakończenia lub być od razu domkniętym, jeśli nie posiada
zawartości:
<element1>
tekst jako zawartość elementu
</element1>
<element2/>
Element może też posiadac atrybuty, które są parami łańcuchów
oddzielonych znakiem równości. Wartość atrybutu musi być objęta w cydzusłów
lub apostrof.
<element nazwa1="wartość1" nazwa2="wartość2">
<pod-element/>
</element>
Oprócz elementów i ich zawartości dokument XML może zawierać zwyczajny
tekst. Jest on, obok wplecionych w niego elementów, częścią elementu
nadrzędnego, wewnątrz którego leży.
Ponieważ nie wszystkie znaki mogą występować w takim tekście dosłownie,
czasami trzeba stosować referencje:
- &
- Znak amperstand "&"
- <
- Znak mniejszości "<"
- >
- Znak więszkości ">"
- '
- Apostrof '
- "
- Cudzysłów "
- &DDD;
- Znak o kodzie podanym jako liczba dziesiętna DDD
- &xHH;
- Znak o kodzie podanym jako liczba szesnastkowa HH
Inne, zwykle rzadziej stosowane rodzaje informacji to:
1. <!-- komentarz -->
2. <?adresat informacje ?>
3. <?xml version="1.0" encoding="UTF-8" standalone="yes"?>
4. <![CDATA[ tekst ]]>
- Komentarz (pomijany przez programy odczytujące, przeznaczony tylko
dla człowieka)
- Processing Instruction - informacja przeznaczona dla programu
odczytującego dokumemt
- Prolog, czyli nagłówek dokumentu XML (tu pokazany przykładowy)
- Sekcja CDATA - jej zawartość traktowana jest tak jak zwyczajny
tekst, ale może zawierać absolutnie dowolne znaki z wyjątkiem
3-znakowej sekwencji zamykającej
Warto wspomnieć jeszcze o dodatkowych standardach powiązanych z XML:
- XPath
- Służy do wybierania fragmentów dokumentu XML; stosowany w XSLT
- XSLT
- Deklaratywny język służący do przetwarzania jednych dokumentów XML
na inne (będzie jeszcze wspomniany w rozdziale 7 - "Języki
programowania")
- Schema
- Służy do opisywania strukury dokumentu opartego na XML
Linki
- Extensible Markup Language (XML) 1.0 (Third Edition)
- Oficjalny opis standardu XML
- XML Tutorial
- Kurs XML na bardzo przystępnej stronie w3schools.com
EBNF
W dalszej części tego rozdziału utworzymy własny format tekstowy i
napiszemy program do jego analizy (parser). Wyobraźmy sobie, że jest to
dziennik zdarzeń (log) jakiegoś programu. Przykładowy fragment dokumentu
wygląda tak:
[2004-02-22 14:26:25] [notice] Exit event signaled. Child process is ending.
[2004-02-22 14:26:26] [notice] Released the start mutex
[2004-02-22 14:26:27] [notice] Waiting for 250 worker threads to exit.
[2004-02-22 14:26:27] [notice] All worker threads have exited.
[2004-02-22 14:26:27] [notice] Child process is exiting
[2004-02-22 14:26:27] [notice] Child process exited successfully.
W tym miejscu należy się krótka dygresja na temat pewnej klasyfikacji
formatów tekstowych:
- Z podziałem na wiersze
- Każdy wiersz jest pewną jednostką podlegającą osobnej analizie (np.
format, który będziemy teraz tworzyli)
- Wolny format zapisu
- Znak końca wiersza jest traktowany jako jeden z białych znaków i może
występować w różnych miejscach nie różniąc się znaczeniem np. od spacji
(np. XML)
Natychmiastowe rozpoczęcie implementacji programu analizującego złożony
format tekstowy (ten jest w miarę prosty, ale na jego przykładzie pokażę
wszystkie istotne rzeczy) byłoby podejściem niemądrym z dwóch
powodów:
- Łatwo można przeoczyć niektóre możliwe sytuacje i wprowadzić do kodu
paskudne błędy ujawniające się tylko wobec pewnych kombinacji
znaków.
- Pisanie programu analizującego bardziej złożony format tekstowy
wydaje się bardzo trudne i przy tym podejściu takie byłoby
faktycznie.
BNF (The Backus-Naur Form) to sposób precyzyjnego opisania gramatyki
bezkontekstowej jakiegoś języka (opisu lub programowania). EBNF (The
Extended Backus-Naur Form) wprowadza do niego elementy składni wyrażeń
regularnych, by umożliwić czytelny, a zarazem zwięzły opis.
EBNF jest trochę podobny do wyrażeń regularnych. Podstawowa różnica
polega na tym, że opis danego formatu składa się z definicji szeregu pojęć,
z których jedne odwołują się do innych.
Zanim przejdziemy do przykładów trzeba podkreślić, że EBNF nie jest
przeznaczony do analizy przez komputer (choć oczywiście można to zrobić).
To tylko precyzyjny opis tworzonego formatu pisany przez nas i dla nas.
Jest to doskonały etap pośredni pomiędzy koncepcją tworzonego formatu,
a implementacją parsera. Jak się okaże w następnym podrozdziale, dzięki
precyzyjnemu opisaniu składni tego formatu pisanie na jego podstawie
parsera staje się zadaniem bardzo prostym.
Składnia EBNF została ustandaryzowana. Jednak w praktyce niemal każdy
(łącznie z konsorcjum W3C, które stworzyło HTML, XML itp.) do definiowania
tworzonych formatów używa własnych konstrukcji. Oto opis naszego formatu
dziennika w EBNF:
S = ' '
EOL = "\r\n" | '\n' | '\r'
date_sep = '-'
time_sep = ':'
digit = ['0'-'9']
number = digit+
year = number
month = number
day = number
hour = number
minute = number
second = number
Date = '[' year date_sep month date_sep day S
hour time_sep minute time_sep second ']'
Type = '[' [^']']* ']'
Text = [^'\r','\n']*
Line = Date S Type (S Text)? EOL?
Możliwe są dwa podejścia. Można albo zaczynać od opisania najprostszych
składników (jak liczba, odstęp itp.) i kostruować z nich bardziej złożone,
albo zaczynać od opisania całości używjąc elementów prostyszch, które
zostaną zdefiniowane dopiero później. Tutaj użyłem pierwszego
podejścia. Przeanalizujmy po kolei ten przykład.
Każda definicja składa się z nazwy, znaku równości i opisu. Opis składa
się z kolejno następujących po sobie składników. Pośród nich mogą znajdować
się elementy zdefiniowane gdzieś indziej.
Najpierw zdefiniowane zostały podstawowe elementy. Spacja, oznaczona
krótko jako "S", została opisana za pomocą pojedynczego znaku. Pojedyncze
znaki obejmuje się w apostrofy. Koniec wiersza "EOL" to jedna z możliwych
sekwencji znaków. Pionowa kreska oznacza alternatywę. Wieloznakowe łańcuchy
obejmuje się w cudzysłów.
Do zdzefiniowania cyfry "digit" użyłem konstrukcji znanej z wyrażeń
regularnych, która oznacza dowolny znak z podanego zakresu. Podobnie można
się domyśleć (znając wyrażenia regularne), że liczba "number" to jedna lub
więcej cyfr.
Składniki daty (rok, miesiąc, dzień, godzina, minuta i sekunda)
zdefiniowane zostały jako synonimy liczby. Wbrew pozorom taka konstrukcja
ma sens. Dzięki niej można będzie np. prosto zmienić definicję miesiąca
na jeden z łańcuchów "Jan", "Feb" itd., jeśli w przyszłości zajdzie taka
potrzeba.
Dalej znajdują się coraz bardziej złożone i ogólne elementy. Spójrz
jeszcze raz na przykładowy fragment dokumentu w naszym formacie. Data
składa się kolejno z otwarcia nawiasu kwadratowego, roku, separatora daty,
miesiąca itd., aż do zamknięcia nawiasu.
Typ komunikatu zdefiniowałem jako
otwarcie nawiasu kwadratowego, zamknięcie nawiasu kwadratowego, a pomiędzy
nimi sekwencja dowolnej ilości (mówi o tym gwiazdka) dowolnych znaków z
wyjątkiem (ptaszek) zamknięcia nawiasu kwadratowego (znak objęty
w apostrofy).
Podobnie test do sekwencja dowolnej ilości dowolnych znaków z wyjątkiem
znaków końca wiersza.
Wreszcie linia, jako podstawowy i największy rekord danych, składa się
ze zdefiniowanych wcześniej części - daty, typu oraz tekstu odddzielonych
spacjami. Zwróć uwagę, że obecność ostatniej spacji i tekstu (jako całości
- nawiasu służą tylko do grupowania) jest opcjonalna. Co by się stało,
gdyby nie była?
Tekst zdefiniowany jest jako dowolna liczba znaków, także zero. Wobec
tego, gdyby po typie informacji nastąpiła spacja i od razu koniec wiersza,
tekstem byłby po prostu łańcuch pusty. Jednak bez tej spacji nastąpiłby
błąd, bo jest wymagana w definicji linii. My zakładamy tutaj, że tekstu
nie musi być.
Koniec wiersza też jest opcjonalny. Dzięki temu ostatnia linia w pliku
nie musi się nim kończyć. Czy nie spowoduje to jednak pominięcia go wtedy,
kiedy wytępuje, np. między wierszami? Nie, ponieważ po to są elementy
opcjonalne (znak zapytania oznacza, że może wystąpić 0 lub 1 razy), że
o ile tylko występują, są odczytywane.
Na tym kończymy omawianie EBNF. Cały ten standard jest prosty i bardzo
użyteczny, a za jego pomocą można opisywać składnię nawet tak złożonych
języków, jak języki programowania, np. C++.
Parsery
Najwyższy czas zdefiniować pojęcie, którego używamy od dawna... Każdy
format tekstowy zawiera, oprócz istotnych danych, także różne nadmiarowe
informacje (jak odstępy i znaki końca wiersza) tworzące jego układ. Same
informacje też są odpowiednio zakodowane (wszystkie w postaci tekstowej) i
nierzadko umieszczone wewnątrz specjalnych znaków (np. cudzysłowów).
To sprawia, że pisząc program musisz uwzględniać składnię danego języka i
niejako wyławiać z dokumentu istotne dane.
Znając specyfikację takiego języka można jednak napisać moduł, który
zamknie w sobie wszelkie zagadnienia obsługi jego składni. Używając takiego
modułu, można otrzymywać z niego tylko istotne informacje i dzięki temu
skupić się na ich przetwarzaniu. To jest właśnie parser.
Warto wprowadzić podział parserów SAX na:
- Czynne
- Po uruchomieniu parser sam odczytuje kolejne informacje i wywołuje
funkcje zwrotne z używającego go kodu
- Bierne
- Użytkownik parsera musi sam żądać od niego odczytywania kolejnych
informacji
Pisząc parser w języku C++ lepiej moim zdaniem wybrać model bierny,
ponieważ w C++ brakuje mechanizmu wskaźników na metody (konkretną metodę
konkretnego obiektu - jak zdarzenia w Object Pascalu w Delphi), który
umożliwiłby wygodną implementację funkcji zwrotnych (callback) w połączeniu
z kodem obiektowym.
Zajmiemy się teraz napisaniem parsera naszego wymyślonego formatu.
Będziemy przy tym korzystali z opisu jego składni za pomocą EBNF, który
został wprowadzony w poprzednim podrozdziale. Przypominam przykładową
linijkę dokumentu w tym formacie:
[2004-02-22 14:26:25] [notice] Exit event signaled. Child process is ending.
Jak działa parser? Jako przykład weźmy odczytywanie pierwszej części
tej linijki -
daty. Pierwszym znakiem jest zawsze otwierający nawias kwadratowy. Możnaby
więc rozpoczynać odczytywanie dopiero od drugiego znaku. To jednak nie jest
dobre rozwiązanie, bo pozostawia poza kontrolą poprawność tego
pierwszego.
Przykładem drugiego często popełnianego błędu byłoby tutaj poszukiwanie
nawiasu zamykającego, a następnie parsowanie zawartego w środku tekstu jako
daty. To podejście jest złe, ponieważ składnia zawartości tego nawiasu
może dopuszczać (choć w tym przypadku nie dopuszcza) istnienie pewnych
elementów, które również zawierałyby taki znak.
Jak w takim razie dokonywać tego parsowania? Wyobraźmy sobie odczytywany
dokument oraz indeks (numer znaku), którego wartość pokazuje na bieżący
znak tego dokumentu. Parser to zbiór funkcji. Każda odpowiada jednemu
elementowi składni formatu zdefiniowanemu w EBNF.
Każda funkcja próbuje
odczytywać kolejne podelementy, z których składa się odczytywany element
zgodnie z jego definicją. Jeśli się to uda, przesuwa indeks za koniec
odczytanego tekstu i zwraca odczytane informacje. Jeśli nie uda się,
pozostawia indeks niezmieniony, co pozwala funkcji nadrzędnej spróbować
odczytać z tego samego miejsca element innego rodzaju.
Poniżej prezentuję kompletny, działający przykład parsera odczytującego
nasz format. Zachęcam do jego analizy. Szczególną uwagę zwróć na to, w jaki
sposób definicje poszczególnych elementów składniowych zapisane wcześniej
w EBNF stały się kodem kolejnych funkcji.
#include <iostream>
#include <sstream>
#include <pxcommon.h>
std::string doc;
bool Parse_Char(size_t* index, char ch)
{
if (*index < doc.size() && doc[*index] == ch) {
(*index)++;
return true;
}
else return false;
}
bool Parse_S(size_t* index)
{
return Parse_Char(index, ' ');
}
bool Parse_EOL(size_t* index)
{
if (*index < doc.size()) {
if (doc[*index] == '\n') {
(*index)++;
return true;
}
else if (doc[*index] == '\r') {
(*index)++;
if (*index < doc.size() && doc[*index] == '\n')
(*index)++;
return true;
}
else return false;
}
else return false;
}
bool Parse_DateSep(size_t* index) { return Parse_Char(index, '-'); }
bool Parse_TimeSep(size_t* index) { return Parse_Char(index, ':'); }
bool Parse_Digit(size_t* index, char* c)
{
if (*index < doc.size() && doc[*index] >= '0' && doc[*index] <= '9') {
*c = doc[*index];
(*index)++;
return true;
}
else return false;
}
bool Parse_Number(size_t* index, int* number)
{
char c;
std::string s;
size_t i = *index;
while (Parse_Digit(&i, &c))
s += c;
if (s.empty())
return false;
else {
*number = px::str2int(s);
*index = i;
return true;
}
}
inline bool Parse_Year(size_t* index, int* year)
{ return Parse_Number(index, year); }
inline bool Parse_Month(size_t* index, int* month)
{ return Parse_Number(index, month); }
inline bool Parse_Day(size_t* index, int* day)
{ return Parse_Number(index, day); }
inline bool Parse_Hour(size_t* index, int* hour)
{ return Parse_Number(index, hour); }
inline bool Parse_Minute(size_t* index, int* minute)
{ return Parse_Number(index, minute); }
inline bool Parse_Second(size_t* index, int* second)
{ return Parse_Number(index, second); }
bool Parse_Date(size_t* index, std::string* date)
{
int year, month, day, hour, minute, second;
size_t i = *index;
date->clear();
if (!Parse_Char(&i, '[')) return false;
if (!Parse_Year(&i, &year)) return false;
if (!Parse_DateSep(&i)) return false;
if (!Parse_Month(&i, &month)) return false;
if (!Parse_DateSep(&i)) return false;
if (!Parse_Day(&i, &day)) return false;
if (!Parse_S(&i)) return false;
if (!Parse_Hour(&i, &hour)) return false;
if (!Parse_TimeSep(&i)) return false;
if (!Parse_Minute(&i, &minute)) return false;
if (!Parse_TimeSep(&i)) return false;
if (!Parse_Second(&i, &second)) return false;
if (!Parse_Char(&i, ']')) return false;
*index = i;
std::ostringstream os;
os << day << '.' << month << '.' << year << ' ' << hour << ':' <<
minute << ':' << second;
*date = os.str();
return true;
}
bool Parse_Type(size_t* index, std::string* date)
{
size_t i = *index;
date->clear();
if (!Parse_Char(&i, '[')) return false;
while (i < doc.size() && doc[i] != ']')
*date += doc[i++];
if (!Parse_Char(&i, ']')) return false;
*index = i;
return true;
}
bool Parse_Text(size_t* index, std::string* text)
{
text->clear();
while (*index < doc.size() && doc[*index] != '\r' &&
doc[*index] != '\n')
*text += doc[(*index)++];
return true;
}
bool Parse_Line(size_t* index, std::string* date, std::string* type,
std::string* text)
{
size_t i = *index;
if (!Parse_Date(&i, date)) return false;
if (!Parse_S(&i)) return false;
if (!Parse_Type(&i, type)) return false;
if (Parse_S(&i)) {
if (!Parse_Text(&i, text)) return false;
}
Parse_EOL(&i);
*index = i;
return true;
}
int main()
{
std::string date, type, text;
size_t index = 0, line = 1;
if (px::LoadStringFromFile("doc.txt", doc)) {
while (Parse_Line(&index, &date, &type, &text)) {
std::cout << "Linia:\n data='" << date << "' typ='" << type <<
"'\n tekst='" << text << "'\n";
line++;
}
if (index < doc.size())
std::cout << "Blad: parsowanie przerwane na wierszu " <<
static_cast<unsigned>(line) << std::endl;
}
else
std::cout << "Blad: nie mozna wczytac pliku" << std::endl;
}
Pisanie takiego parsera, mając przed oczami precyzyjny opis formatu
w EBNF, jest naprawdę bardzo proste, niemal mechaniczne, a po napisaniu
taki parser od razu działa poprawnie! Wynik działania tego programu
dla przedstawionego w poprzednim podrozdziale przykładowego dokumentu
wygląda tak:
Linia:
data='22.2.2004 14:26:25' typ='notice'
tekst='Exit event signaled. Child process is ending.'
Linia:
data='22.2.2004 14:26:26' typ='notice'
tekst='Released the start mutex'
Linia:
data='22.2.2004 14:26:27' typ='notice'
tekst='Waiting for 250 worker threads to exit.'
Linia:
data='22.2.2004 14:26:27' typ='notice'
tekst='All worker threads have exited.'
Linia:
data='22.2.2004 14:26:27' typ='notice'
tekst='Child process is exiting'
Linia:
data='22.2.2004 14:26:27' typ='notice'
tekst='Child process exited successfully.'
Omówienia wymaga jeszcze pojęcie tzw. zachłanności. W naszym przykładzie
treść typu zdefiniowana została jako ciąg dowolnych znaków z wyjątkiem
znaku oczekiwanego jako jej zakończenie (zamknięcie nawiasu kwadratowego).
Dzięki temu można było odczytywać znaki zachłannie - tak dużo, jak
to możliwe.
Można zastosować inne podejście. Treść typu można zdefiniować jako ciąg
absolutnie dowolnych znaków. Z każdym kolejnym odczytywanym znakiem najpierw
sprawdzać, czy nie następuje zakończenie (zakończeniem nie musi być jeden
znak - może być cała sekwencja, którą próbuje odczytać osobna funkcja),
a dopiero w przeciwnym wypadku traktować go jako dalszy ciąg łańcucha.
Jak widać, zagadnienie zachłanności sprowadza się więc do kolejności
sprawdzania różnych możliwych elementów w danym miejscu.
Na zakończenie tego rozdziału wypada jeszcze napisać kilka słów
o decyzjach, jakie stoją przed twórcą formatu i autorem parsera. Mówiąc
ogólnie, trzeba znaleźć rozsądny kompromis pomiędzy kontrolą i
sygnalizowaniem błędów, a wydajnością (szybkością) parsera. Należy przy tym
uwzględnić przewidywane zastosowanie (czy wydajność jest tam sprawą
kluczową?).
Drugim problemem jest decyzja w sprawie traktowania błędów składniowych.
Możliwe są tutaj dwa podejścia:
- Zgłaszać błąd
- Napotkanie pierwszego błędu powoduje zaprzestanie dalszego
parsowania. Należy zgłosić błąd podając jego rodzaj i miejsce wystąpienia
(wiersz, kolumna, numer znaku oraz fragment w okolicy tego miejsca).
W ten sposób reagują np. parsery XML.
- Parsować dalej
- Parser próbuje poradzić sobie z błędem przeskakując do jakiegoś
dalszego miejsca i parsować dalej,
- zgłaszając ewentualnie kolejne błędy (np. kompilatory C++ i
nowszych wersje Delphi) lub
- po prostu przetwarzając wszystko, najwyżej niezgodnie
z oczekiwaniami (np. przeglądarki WWW parsujące HTML).
Wbrew pozorom, każde z tych rozwiązań ma sens w niektórych
zastosowaniach. XML musi być zawsze doskonale poprawny, bo takie jest jego
założenie. Kontynuacja parsowania podczas kompilacji pozwala kompilatorowi
odnaleźć, a programiście poprawić wiele błędów na raz. Strona HTML pokaże
się i prawdopodobnie pozostanie czytelna mimo ewentualnych błędów
składniowych.
Trzecim problemem jest sprawdzanie zakresu dozwolonych znaków. Pojawia
się pytanie, jakie znaki dopuszczać w treści pewnych nazw, tytułów
itp.?
- Tylko z dozwolonego zakresu
- Lepsza kontrola błędów, ale zarazem pewne ograniczenia (co z literami
polskimi czy japońskimi?) i więcej pracy ze sprawdzaniem każdego
znaku
- Dowolne z wyjątkiem tych oczekiwanych jako zakończenie
- Gorsza kontrola błędów, ale większa elastyczność i szybsze
parsowanie
Języki programowania
Pojęcie języka programowania z pewnością jest ci (jako czytelnikowi,
który dotrwał aż tutaj :) znane, dlatego nie będziemy go definiowali.
Musimy jednak opisać kilka spraw związanych z ich strukturą oraz wprowadzić
pewien podział.
O językach programowania
Języki programowania dzielą się na generacje:
- I generacja - kod maszynowy
- Polecenia procesora najniższego poziomu
- II generacja - asemblery
- Bezpośrednia, tekstowa reprezentacja rozkazów maszynowych
- III generacja - języki symboliczne
- Dzielą się na:
- Języki liniowe
- Program to płaska lista poleceń i instrukcji skoku (np. Fortran,
Basic w dawnych wersjach)
- Języki skrukturalne
- Program składa się z opisu danych i funkcji, które na nich operują
(np. C, Pascal w dawnych wersjach)
- Języki obiektowe
- Program składa się z klas definiujących pola i metody i
reprezentujących określone pojęcia (np. C++, Object Pascal)
- IV generacja - języki idealnie nieproceduralne (np. SQL)
- Nowe metody programowania, specjalizowane do określonych
zastosowań
Z punktu widzenia budowy języka programowania istotne są dwa pojęcia i
ich rozróżnienie. Pierwszym są instrukcje. Instrukcja to składnik ciała
funkcji o określonej budowie przeznaczony do wykonania. Instrukcje
wykonywane są po kolei, ale mogą zawierać wewnątrz inne instrukcje, a także
zmieniać przebieg sterowania (pewne instrukcje pominać lub powtarzać) itp.
Rozważmy przykład kodu w C++:
void MojaFunkcja()
{
if (ziemia_jest_plaska == true) {
uwazaj_zeby_nie_spasc();
}
while (!blad()) {
zajmuj_pamiec();
if (rand()%10 == 0)
spowoduj_blad();
}
}
Najpierw wykona się pierwsza instrukcja warunkowa, a następnie
pętla.
Drugim ważnym pojęciem jest wyrażenie. Wyrażenie posiada (zwraca)
wartość jakiegoś typu. Może być zagnieżdżane wewnątrz innego wyrażenia,
a także w pewnych przewidzianych miejscach w instrukcji, np.:
if ( 2*2 == sqrt(16) ) {
std::cout << "Ta matematyka naprawdę działa :)" << std::endl;
}
Mnożenie dwóch liczb całkowitych jest wyrażeniem, które daje w wyniku
również liczbę całkowitą. Wywołanie funkcji jest wyrażeniem, które zwraca
taką wartość i takiego typu, jak zwróciła ta funkcja. Wreszcie porównanie
jest wyrażeniem, które zwraca wartość logiczną (true lub false).
W szerszym kontekście zwykła stała dosłowna 2 także jest wyrażeniem,
bo posiada wartość jakiegoś typu. Każde wyrażenie jest instrukcją - użyte
w takiej roli pozostawia swoją wartość, zwróconą po jego wykonaniu jako
całości, niewykorzystaną.
Języki programowania można też podzielić na:
- Kompilowane
- Kod źródłowy jest kompilowany do kodu maszynowego wykonywanego
bezpośrednio jako niezależny program (plik EXE)
- Interpretowane
- Kod źródłowy jest wykonywany przez interpreter
Jednak obecnie ten podział jest coraz mniej sensowny. Nawet instrukcje
maszynowe są w niektórych procesorach tłumaczone na wewnętrzny mikrokod
i dopiero wykonywane. Z drugiej strony prawie nigdy nie zdarza się, by
kod źródłowy jako tekst interpretowany był bezpośrednio. Zawsze najpierw
jest rozkładany, przynajmniej na drzewo składniowe i nierzadko tłumaczony
(kompilowany?) do postaci pewnego kodu pośredniego (bytecode). Mówi się
wtedy czasem o półkompilacji, a zamiast interpretowania używa się terminu:
wykonywanie w wirtualnej maszynie. Jak widać więc, to wszystko
jest względne.
Języki można podzielić jeszcze inaczej na:
- Imperatywne (sterowane kodem)
- Wykonywanie kolejnych instrukcji kodu powoduje sterowanie przepływem
danych (wszystkie tradycyjne języki programowania)
- Deklaratywne (sterowane danymi)
- Przychodzące dane powodują wywoływanie pewnych elementów kodu (np.
XSLT)
Czasami problemem jest dokonanie wyboru pomiędzy programowaniem,
a opisywaniem. Jako przykład wyobraźmy sobie grę, która potrzebuje
zapisanych w pliku definicji różnych potworów. Obok koloru, nazwy czy siły
każdego z nich potrzeba zdefiniować jego zachowanie. Jak je zapisywać?
- Najprostszym podejściem jest wpisanie kilku możliwych zachowań do
kodu samej gry, z ewentualnymi parametrami (np. agresywność) i
zapisywanie z każdym potworem, którego rodzaju zachowania ma używać.
- Rozwiązaniem pośrednim pomiędzy opisywaniem a programowaniem jest
pojęcie zapadek (ang. "triggers"). Każda zapadka ma określone zdarzenie,
które powoduje jej wywołanie (wraz z ewentualnymi warunkami) oraz listę
kolejnych akcji do wykonania. Przykładowo mechanizm zapadek użyty został
w edytorach map do gier Warcraft i StarCraft firmy Blizzard.
- Najbardziej złożone i elastyczne, ale nie zawsze potrzebne
rozwiązanie to zastosowanie najprawdziwszego języka programowania -
tzw. języka skryptowego, którego kod interpretowany wewnątrz gry będzie
wchodził w interakcję z wirtualnym światem, np. sterując zachowaniem
danego potwora.
Linki
Oto języki skryptowe, które można osadzać w swoich programach:
- LUA
- Bardzo mały, prosty, szybki; przeznaczony specjalnie do osadzania;
wyróżnia się możliwością rozbudowy jego składni o nowe, potrzebne
elementy
- Python
- Bardzo rozbudowany i potężny język o ciekawej składni
- TCL
- Bardzo popularny język; ma nieprzyjemną składnię
Wyrażenia matematyczne
Po tych wiadomościach wstępnych dotyczących języków programowania
rozpoczynamy omawianie metod ich parsowania. Ponieważ jednak ten
temat jest tak trudny i
obszerny, że zasługuje na osobny artykuł (lub nawet książkę),
ograniczę się w tym rozdziale do ogólnego omówienia podstawowych
zagadnień.
Czasami wystarczy zapewnić ewaluację (czyli obliczanie wartości)
wyrażeń, bez pełnej składni języków programowania. Najprostszym przykładem
może być program do rysowania wykresów funkcji.
Za pomocą samych wyrażeń można zdziałać bardzo wiele. Przykładowo
warunki można zaimplementować w postaci wyrażenia złożonego z 3
podwyrażeń, z których zwracana jest wartość drugiego, jeśli wartością
pierwszego jest prawda i wartość trzeciego, jeśli wartością pierwszego jest
fałsz, np.:
x + 2 + if( x > 3, 10, -10 )
Podczas parsowania wyrażeń matematycznych pojawia się problem priorytetu
operatorów, znany ze szkoły jako kolejność wykonywania działań. Polega on
na właściwym ustawieniu ważności poszczególnych podwyrażeń w przypadku,
kiedy kolejność ich obliczania nie jest wymuszona za pomocą nawiasów,
np.:
2+2*2 to 2+(2*2)
Innym problemem jest łączność operatorów. Określa ona kolejność
obliczania podwyrażeń równorzędnych od lewej lub od prawej strony. Podczas
ewaluacji zwykłych wyrażeń matematycznych łączność jest zawsze
lewostronna, ale nie zawsze musi tak być. Np. przypisanie (które
w C++ też jest wyrażeniem, a zwraca wartość przypisywaną) jest łączne
prawostronnie. Oto przykłady:
2+3+4+5 to ((2+3)+4)+5
x=y=z=0 to x=(y=(z=0))
Przed obliczeniem wyrażenie można zamienić na drzewo. Takie
przedstawienie umożliwia wiele ciekawych rzeczy, np. obliczanie
pochodnych.
2+2*2
+
/ \
2 *
/ \
2 2
Takiej zamiany, wraz z poprawnym rozpoznaniem priorytetu operatorów,
może dokonać zwyczajny parser napisany na podstawie
odpowiednio ułożonego opisu w EBNF, np.:
wyrażenie = (wyrażenie '+' składnik) | (wyrażenie '-' składnik)
| składnik
składnik = (składnik '*' czynnik) | (składnik '/' czynnik) | czynnik
czynnik = ('(' wyrażenie ')') | ('-' czynnik) | liczba | zmienna
Pewne znaczenie podczas parsowania i ewaluacji wyrażeń ma odwrotna
notacja polska (ang. "Reverse Polish Notation", w skrócie ONP lub RPN). Jest ona
sposobem zapisywania wyrażeń, w którym symbol wykonywanej operacji
umieszczony jest po operandach (a nie pomiędzy nimi jak w konwencjonalnym
zapisie). Zapis ten pozwala na całkowitą rezygnację z użycia nawiasów
w wyrażeniach, jako że jednoznacznie określa kolejność wykonywanych
działań. Przykład:
Normalnie : (2+3)*5
ONP : 2 3 + 5 *
Jest to dobry sposób płaskiej reprezentacji przedstawionego wyżej
drzewa.
Algorytmy dokonując analizy wyrażeń często przekształcają je na odwrotną
notację polską. Bardzo ułatwia ona wykonywanie obliczeń z nawiasami i
zachowaniem kolejności działań. Zarówno algorytm konwersji notacji
konwencjonalnej (infiksowej) na odwrotną notację polską (postfiksową),
jak i algorytm obliczania wartości wyrażenia danego w ONP są bardzo proste
i wykorzystują stos.
Kod
W przeciwieństwie do języków opisu, kod języków programowania nie jest
parsowany bezpośrednio z łańcucha. Najpierw dokonywana jest tokenizacja,
czyli zamiana na ciąg tokenów. Oto przykłady tokenów różnego rodzaju
(każdy token składa się z rodzaju i zależnej od niego treści):
identyfikatory x
moja_funkcja
operatory +
!=
liczby 9
314.15e-2
łańcuchy "ble"
"\r\n"
Dopiero taki ciąg tokenów jest rozkładany na drzewo. Następnie takie
drzewo jest na różne sposoby sprawdzane, np. pod kątem zgodności typów.
Wreszcie może zostać skompilowane do jakiegoś płaskiego kodu, który będzie
wykonywany (np. do kodu maszynowego). Można też wyobrazić sobie
wykonywanie bezpośrednio tego drzewa, bez jego spłaszczania.
Program przetwarzający kod musi dokonywać optymalizacji. Niemądrze
byłoby pozostawiać wyrażenie 2+2 do każdorazowego obliczania podczas
wykonywania zamiast zastąpić go pojedynczą wartością 4, skoro da się ją
wyznaczyć już na etapie kompilacji. Warto usuwać nieużywane zmienne,
funkcje, moduły... Łatwo można sobie wyobrazić wiele różnych
optymalizacji.
Linki
- The Lex & Yacc Page
- Narzędzie to automatyzacji tworzenia parserów
- Kompilatory. Reguły, metody i narzędzia
- Książka o pisaniu kompilatorów; autorzy: Aho Alfred V., Sethi Ravi, Ullman Jeffrey D.; wydawnictwo: WNT
Ciekawoski
Na koniec rozdziału o językach programowania opiszę kilka ciekawostek,
które są raczej mało znane, choć z punktu widzenia tematyki tego artykułu
z pewnością godne uwagi.
Języki ezoteryczne
Istnieje bardzo wiele języków programowania. Jedne są uniwersalne,
inne specjalistyczne. Jedne stare i już dawno zapomniane, inne cieszą się
niesłabnącą popularnością, jeszcze inne przeżywają swój chwilowy rozkwit
czy też dopiero czekają na swój czas.
Są też języki stworzone ot tak, dla zabawy. Ich autorzy zakładają
(całkiem słusznie), że dla wielu pasjonatów programowanie jest dobrą
zabawą i wymyślają najróżniejsze, nietypowe sposoby na programowanie.
Angielskie "esoteric" znaczy "ezoteryczny", ale też "poufny",
"wtajemniczony". Języki ezoteryczne są więc adresowane tylko
do prawdziwych maniaków programowania. Oto niektóre z nich:
- Brainfuck
- Język absolutnie minimalistyczny, podobny trochę do maszyny Turinga.
Składa się tylko z 8 poleceń. Oto program wypisujący "Hello world":
>+++++++++[<++++++++>-]<.>+++++++[<++++>-]<+.+++++++..+++.[-]
>++++++++[<++++>-]
<.#>+++++++++++[<+++++>-]<.>++++++++[<+++>-]<.+++.------.--------.
[-]>++++++++[
<++++>-]<+.[-]++++++++++.
- Malbolge i Dis
- Język stworzony z założeniem, że programowanie powinno być jak
najtrudniejsze. Oto program wypisujący trzy szóstki:
*>>*|{{{!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!{**
- Funge
- W językach z tej rodziny (Befunge, Unefunge, Trifunge) kod składa się
nie z listy rozkazów, ale z tablicy rozkazów (dwu- lub nawet trójwymiarowej).
Oto program wypisujący "Hello world!":
v
>v"Hello world!"0<
,:
^_25*,@
Zaciemniony kod
Jedyny słuszny sposób pisania kodu źródłowego, którego uczymy się dążąc
do doskonałości, nie jest jedynym możliwym. Niektórzy lubią wyczyniać
najróżniejsze rzeczy nie tylko z treścią, ale i z formą swojego kodu.
Poniższa funkcja pochodzi ze wstępu do książki pt. "Perełki programowania
gier, tom 3". Po dołączeniu biblioteki "stdio.h" rysuje (oczywiście
tekstowo, na konsoli :) znany fraktal - zbiór Mandelbrotta. Takie krótkie
kody nadają się też jako sygnatury do listów elektronicznych.
f(){int k;float i,j,r,x,y=-16;while(puts(""),y++<15)for(x
=0;x++<79;putchar(" .:-;!/>)|&IH%*#"[k&15]))for(i=k=r=0;
j=r*r-i*i-2+x/25,i=2*r*i+y/10,j*j+i*i<11&&k++<111;r=j);}
- The International Obfuscated C Code Contest
- Konkurs na najbardziej zaciemniony kod
Wojny rdzeniowe
Wojny rdzeniowe (ang. "CoreWars") to stara zabawa programistów. Programy
napisane w specjalnym języku podobnym do Assemblera (tzw. "RedCode") są
równolegle wykonywane w wirtualnej maszynie. Współdzielą one jeden obszar
pamięci i jedyne, co mogą robić, to operować na tej pamięci. Zadaniem
programu jest takie jej zmodyfikowanie, aby kod przeciwnika wykonał
niedozwoloną operację. Oto prosty program do wojen rdzeniowych znany jako
"Dwarf":
ADD #4, 3
MOV 2, @2
JMP -2
DAT #0, #0
Zakończenie
Wszędzie wokół nas coraz więcej jest multimediów: grafiki, dźwięku,
video. Tymczasem tekst jest i na zawsze pozostanie istotnym, a w wielu
miejscach najważniejszym czy najlepszym sposobem komunikacji,
przechowywania i przesyłania informacji, a także programowania
komputera.
Niektóre zaprezentowane tutaj tematy są, jak to się mówi, niszowe.
Znanie niewielu ludziom, opisywane w Internecie w pojedynczych, niedbałych
dokumentach HTML, pozostają poza kręgiem zainteresowania większości ludzi
i dużych, "poważnych" serwisów. Niech tak pozostanie. To naturalne,
że tekst jest mało atrakcyjny.
Możliwe więc, że ASCII Art, gry tekstowe czy udziwnione języki programowania nie
wzbudziły w tobie większego zainteresowania. Mam jednak nadzieję, że przynajmniej
dostrzegasz istotną rolę, jaką tekst i jego przetwarzanie odgrywa
w komputerze.
Ten artykuł stanowi przegląd całej mojej wiedzy, jaką zebrałem
podczas wielu lat mojego zainteresowania wszystkim, co tekstowe. Jednak
nikt nie może powiedzieć, że wszystko, co zrobił, osiągnął wyłącznie dzięki
sobie. Pragnę więc podziękować kilku osobom. Jako pierwszy, na wspomnienie
zasługuje g[R]eK. To on nauczył mnie tej trudnej sztuki parsowania.
Dziękuję mu za nasze długie rozmowy na "priv" oraz za całą naszą wymianę
wiedzy i poglądów.
Na podziękowania zasługuje również Xion, który niestrudzenie pisząc
swój megatutorial daje dobry przykład i pokazuje swoim postępowaniem,
że warto dzielić się z innymi swoją wiedzą, a nie tylko ją
wykorzystywać. Pozdrowienia otrzymuje też gemGreg, DexteR (AyuFan) i
wszyscy fajni ludzie z Warsztatu. To wszystko dzięki wam i dla was! :)
Na zakończenie pokażę jeszcze jedną ciekawostkę. Jeśli jesteś prawdziwym
maniakiem komputerów, możesz stworzyć własną sygnaturę w specjalnym kodzie,
która będzie opisywała twoją osobę. Ja swojej jeszcze nie stworzyłem...
- The Geek Code
Adam Sawicki "Regedit"
2004-02-29
www.programex.prv.pl
www.regedit.risp.pl
|
